Buying a new laptop? Get something with a Centrino sticker. It'll have an Intel processor, chipset, and an Intel wireless card. Intel wireless is the only built-in wireless I've found with which you are guaranteed 100% compatibility out of the box.
Thinking about adding wireless to a desktop or laptop? Go with something with a Zydas chipset. They're USB so you can take them with you, unlike PCI cards. Also, quite a lot of them (the ones marked green on that page) have full support for encryption (yes, up to WPA2) and work with NetworkManager and Feisty out of the box. The TrendNet TEW-424UB should work just fine and is very affordably priced. Another good choice is the ZyXEL G-220. For laptops which have built-in wireless, you should be able to buy Intel Pro/wireless 3945ABG Network Connection - Network Adapter - Mini-pci Express or Intel PRO WIRELESS 2915ABG-802.11 A/B/G Mini-PCI ( WM3B2915ABGNAX ) and replace your old card.
More than just the two I recommend will work for you, depending on your needs. If you don't need WPA or WPA or if you're willing to switch to Wifi-Radar or some other alternative to NetworkManager, your options are much wider. If you don't need WPA/2, a Broadcom-based card or any card made by Cisco should work fine for you, too. However, if you just want something that will work immediately with NetworkManager and can take any kind of encryption you throw at it, this is for you.
If those ideas don't appeal to you, Passys has a list of thousands of wireless devices which can be sorted by chipset, manufacturer, or interface. It tells you what driver you need, and what model uses it. If there are different directions for different versions of a device, the Vendor/Product IDs (type "lspci" to check yours) are listed. It's a great resource. Then, compare to NetworkManager's compatibility list. There will be a lot rated "green" on Passys which are incompatible with NetworkManager (see below for why) for WPA, so make sure you pay attention. I'd suggest staying away from things that use Prism. The Orinoco driver fights with the hostap driver for control of your card, and then it doesn't work without blacklisting one of them. And that's not zero-effort. Printing out a list of the Atheros-chipset-based cards to take to the store is a good idea too. Any "green"-rated Atheros cards will work with NetworkManager.
If you're wondering, like I'm sure many are, why wireless on Linux is so weird, Val Henson recently answered that question on a LinuxChix IRC channel where she gave the first (of, we hope, many) "The Guru Is In" talk. I can't quote her since LinuxChix IRC is not logged, and I didn't save a log on my computer (and I'm not on my own computer right now anyway). What she said, though, is that there is no consensus as to how wireless should be done. There are a few different approaches being used by different teams working on different drivers. Since they haven't all agreed on one way to do it, the user has different hoops to jump through for different cards, chipsets, and drivers, and until they DO unite in one method, we're stuck with how it is right now. You can see this in play by looking at that Network Manager page. Under RaLink, it says "While the driver supports WPA, it does not use Linux Wireless Extensions for WPA support, which is required for NetworkManager." NetworkManager requires that WEXT be used for WPA on the driver. Some drivers do that, some drivers don't. All the people who can't get WPA with NM but get it with Wifi-Radar, that's why. Try to convince the team writing your driver to implement WEXT, and if they do, you'll end up being able to use NetworkManager. As long as the devs writing wireless drivers don't all agree to use one way to interface with the rest of the OS, different GUIs will be needed for different drivers. If they want to implement more than one so you can use Wifi-Radar OR NetworkManager, that's good too, but some sort of standard needs to happen.