How do you troubleshoot wireless woes?

In slightly random order:

• power cycle your wifi router. if it's plugged into an ethernet modem, power cycle both - starting with the ethernet modem (wait till you see its "connection" light come on)
• if you're using combined 802.11g/n (or 802.11b/g) on the router, are you sure all your hardware is 802.11n (or all 802.11g?) set the router to N only (or G only), and find out for sure
• google the "+[router make/model] +[computer/wifi card]" just a brief glance at the results. Some hardware combinations will just never work, or have quirks
• logon to your router's config page and update its firmware, it only takes a few minutes
• download a wifi scanning utility (war-driving utility) and look for a channel that as few as possible of your neighbors are using
• Unless all your hardware was purchased in the same country, check that your wifi router is broadcasting on a channel between 1 and 11
• try different channels and see how they affect your reception, there's not much point switching channels that are less than 3 apart (try 1,4,7 and 10)
• turn off any proprietary "speed boosting" protocols (with names like nitro+ or turbo+), unless both your card and router support them. they can mess with connectivity
• avoid using a cordless phone (or cordless phone base station, baby monitor, wireless camera, etc) near the computer - they can interfere with your network
• check that antennas are properly installed (both the finicky ones on your 802.11 card, and the bulky one that ships with some routers) If one of the three cables on your notebook's 802.11n wifi card wasn't affixed, you'll still be able to connect - kinda.
• troubleshoot the physical environment. Is there anything iffy between you and the router? thick walls, panes of thick glass, metal posts in walls: all bad
• check that you're really connected to the network you thought you were. Eg: if your SSID is the default ("NETGEAR" anyone?) than your computer might have joined your neighbor's weak open wifi network
• try switching from WPA to WEP (yuck, WEP) - some hardware combinations work better using one type of encryption than the other (but if you already googled, as i suggested, then you would likely already have seen other people posting this for your brand of router)
• if you have a wifi router plugged into an ethernet modem make sure only one of them is doing NAT and the other is in bridge mode (i doubt you would miss this, splattne, but for anyone else reading this). NAT over NAT can cause quirky behavior
• if you're using WDS, check your configuration to make sure all the roles are configured appropriately - if you have a repeater that thinks it should be talking to the wrong router, you'll have network issues
• there's always Tomato

One answer states: "logon to your router's config page and update its firmware, it only takes a few minutes"

This is bad advice. Don't make this choice lightly. Make sure you have an actual real reason (ie the release notes specifically say it fixes your problem) and not just a hope that it might make things better.

Certain companies firmware upgrades (eg Netcomm) have a track record of unreliable flawed upgrade procedures and will often leave you with a dead equipment, EVEN if you follow the documented process carefully and in detail.

But the biggest tip, before doing anything else, is do a Google search for "your equipment name" firmware, and see how many others have tried an upgrade and had problems with that equipment. Also include the version you are upgrading to, to see if there are problems specific to it.

Some Ideas:

1) Change the wireless channel on the wireless router/WAP (fixes interference problems)

2) Update the drivers on the wireless NIC's / firmware on the router

3) Point the antennas on the wireless router in a different configuration

4) Knock down walls :)

A spectrum analyzer may be useful in cases where you have ruled out the obvious issues. The Wi-Spy is a relatively inexpensive choice.