Ye Olde Infocomme Shoppe is an excellent place here in the U.S. that buys and sells Infocom items.

the border zone is the German counterpart to the Ye Olde Infocomme Shoppe, but is a separate endeavor.

The Infocom Cornershop is the U.K. counterpart to the Ye Olde Infocomme Shoppe, but is also a separate endeavor.

Game Trading Zone is a free service that helps "computer and video game owners to trade games they don't play anymore for ones they want."

Mr. Bill's Adventureland (formerly Mr. Bill's Adventure Game Website) has a Places to Buy Games (worldwide) page that can assist you in your search.

Similarly, Eric Sansoni's Play Infocom Games Cheap! webpage lists many places worldwide where you can look. This is the site that Peter Scheyen of The Unofficial Infocom Home Page recommends.

Stephen Granade wrote an article for About.com that discussed finding Infocom games and which games were in which Activision re-release. I've made a cross-reference guide that adds what's in The Masterpieces of Infocom.
(When Stephen gets the article transferred to the new Brass Lantern site, I'll provide a link to the article.)

Tom Mage is primarily known for his Ultima page, but he does have some Infocom items for sale or trade.

Activision's new Value Publishing website indicates that they are going to sell Return to Zork, Zork Nemesis and The Zork Collection. This last item is the nine of the Zork-related text adventures that appears briefly for sale on Amazon.com.

CDAcess.com has several of the Zork games, including three of the Activision "Collections" re-releases on CD-ROM.

Interdata Developments in the UK has The Masterpieces of Infocom CDs in stock. The also have information on the two Lost Treasures of Infocom collections.

Camelot Computer Bookstore in Canada has Zork Nemesis and Zork: Grand Inquisitor, and the companion book for Return to Zork.

Auction websites: BidVille, Half.com, EBay-US, EBay-UK, EBay-Australia, EBay-Canada, Yahoo-US, and Yahoo-UK.
Search for "Infocom" or the specific title (which sometimes turns up extra results that a generic search like "Infocom" doesn't).

Amazon.com does have software for sale. On the US website, a search in November for "Zork" turned up about 200 items in their Books, Auctions and zShops, including a book by author Eric Zork Alan. On the UK website that same search turned up about 110 items.

Route 49 Online Sales has Legend Entertainment's Eric the Unready and Fredrick Pohl's Gateway for sale.

Until September 2000, The Masterpieces of Infocom was available as an electronic download for about US$16.00 from a few online stores. The consensus of the rec.games.int-fiction newsgroup was that this gave you the programs and all 3 PDF files (Manuals, Hints and Maps).
All three places had the five Collections re-releases for downloading also, but Masterpieces was the better value.

At the moment, Interdata Developments is the only store I am aware of that has the CD for sale. Activision USA had Masterpieces in their online store for about 3 weeks this past April, but it's sold out again. Activision in Germany DID had Masterpieces of Infocom for sale in their online store around October 2000, but they only ship to addresses inside Germany.