Obviously, you need a wireless LAN device which is supported by Linux, and I
recommend that it is supported natively.
I've got the following devices to work under Linux:
Cardbus - Netgear WG511 (Vendor 0x000b, Device 0x3890) - Important: it MUST be made in Taiwan. No, this is not a joke. Made in China won't work, because they got a different chipset.
USB - Zyxel ZyAir B-220 (Vendor 0x0586, Device 0x3400) which uses chipset VT22387
USB - Fritz!WLAN N (Chipset AR9170 - 802.11 a/b/g/n)
mini PCIe - Atheros AR5B95 (Chipset AR9285 - 802.11 b/g/n)
mini PCIe - Atheros AR5BHB92 (Chipset AR9280 - 802.11 a/b/g/n)
You might be able to use devices not supported natively, too,
using ndiswrapper or LinuxAnt.
Setup
The different devices require different setup and of course each its own driver.
Some of the drivers are in the kernel main tree now, some not, like the AT76C503A.
Here are instructions for each of the devices mentioned above:
Prism 54 based devices, like Netgear WG511
Orinoco based devices, like Siemens I-Gate, are included in the kernel main tree