Since this has long been an area of trouble for Linux users, it will be worth your while to make sure ahead of time that you get Linux-compatible wireless hardware. Until Broadcom's new brcm80211 driver is widely incorporated, this generally means making sure you have compatible wireless hardware from Intel or Atheros.

Graphics

This is another area of potential trouble for Linux users, so you'll want to make sure your laptop's video card and 3D acceleration are fully compatible. This is one area where buying from a Linux-specific laptop vendor can make your life easier--they'll worry about this for you and make sure your graphics work.

Processor

As the brain of your laptop, the CPU will determine its responsiveness and performance in completing the tasks you give it. If you're planning to go Linux-only, this is a less critical consideration, but if you're aiming to dual-boot or use high-end applications, you'll want to get something more powerful.