1) Empty your trash. There may be a bunch of files you think you deleted, but they're still hanging around in the trash.
2) Check swap space. Launch Activity Monitor (it's in your /Applications/Utilities/ folder), select the "System Memory" tab and check how much is listed next to "Swap used" -- you can reclaim that space by rebooting. This is only a temporary gain (if your computer starts to swap again, the space will be used again), but it may help in a pinch.
3) Run periodic cleanups. If your computer isn't left on 24/7, it may not catch up on routine maintenance that cleans out system logging files and other under-the-hood bits (although, in versions of Mac OS X from 10.4 onward, the system should run those cleanup passes automatically if it's asleep when they would normally be active). Launch Terminal.app (also found in the Utilities folder), and paste in these commands (you will need to enter your administrator password):
sudo /usr/sbin/periodic weekly
sudo /usr/sbin/periodic monthly
sudo /usr/sbin/periodic daily
That should take care of any out-of-control log files. Be extremely careful with the sudo command, as it is possible to do some real damage if you begin experimenting.
4) Check /Volumes/. This has caught me a couple of times. Here's what happens: you're copying files to an external drive or making a clone of your boot drive, and something goes wrong. The drive disconnects, but the operating system doesn't notice, so it creates a folder in /Volumes/ and copies the information there. You think it is going onto the external drive, but in fact, it's just being copied onto your hard drive.
You can easily navigate to your Volumes directory in the Finder: go to the Go menu, choose Go to Folder, type in "/Volumes" and hit Return.
5) Use Spotlight to look for large files. It may not be immediately obvious, but Spotlight can be used to find files based on size. You just have to tell it that's what you want to search for. In Finder, enter the search box either by clicking into it, or type ⌘ + F to open the Spotlight search window:
Select "Kind" and a drop-down will appear, showing several search criteria. Select "Other..." from that list, and this window will appear:
Note that I have typed "size" into the box at the top-right of that window, and Spotlight is only showing me search attributes that include the word 'size' anywhere in the description. Select the "Size" attribute, and if you want it to appear in that drop-down, click the "In Menu" box as shown above.
Once you have Size as an available attribute, search for large files. I find 1 GB is a good place to start, but you may want to start lower. Note that this is searching for individual files that are greater than 1 GB. Your iTunes collection may be several gigabytes, but it won't appear here because each file inside that collection is smaller. The same is true for iPhoto libraries and other "packages" in OS X.
Here are the results from my computer. The "VTS" files are DVDs that I have 'ripped' to my hard drive, and there's the video from Apple's special event. I've watched that now and probably won't watch it again (sorry, Steve), so that's safe to delete. I can always re-download it later if I change my mind.
6) Use a "disk usage" app to visualize where your hard drive space is used.
I like OmniDiskSweeper, which I've written about previously, because it's simple: select a folder (either your hard drive, your home folder or anything else), and it will sort all of the sub-folders into a clickable list much like Finder's "Column View" where you can drill-down and examine them. Note that if you use Time Machine, the sizes may actually be shown larger than they are, but it's still useful for tracking down space hogs.
There are several free options if you don't like OmniDiskSweeper: Disk Inventory X, GrandPerspective and JDiskReport to name a few. Each has its own way of displaying the information. I happen to like OmniDiskSweeper, but there's no reason not to check out the other three free options as well.
There's also the $20 DaisyDisk in the Mac App Store, and TUAW will have a review of it available soon.
Update: There are several good suggestions in the comments below. Be sure to check them out!