A Unix-based OS such as OS X requires hard drive space for log and cache files; this can take anywhere from 64MB to 2GB depending on how much RAM you have, how long since the cron maintenance tasks last ran, whether anyting is causing large write operations to the various logs, and so on. As a rule of thumb, you don't want an OS X Mac to drop below about 5GB free space, minimum; a oft-cited ballpark of keeping 10 to 15% of the hard drive free allows for user-created data and allows some safety margin.
If a Unix computer fully runs out of space, the computer can fail to start normally. You'd then face starting in single-user mode (hold the command and s keys down at startup), which puts you in a Unix command line interface. It's possible to use Unix commands to navigate around and search for unnecessary files to delete, but doing so if definitely non-trivial.
While written for Tiger,
Francine: A Miscellany of Mystifying Tiger Problems has some useful tips you can try.
If you moved several GB to the Trash and tried to empty the Trash while the Mac's hard drive was nearly full, that effort may have unintentionally corrupted the disk directory. Boot from your OS X Install disc to launch Disk Utility from the Installer menu, and run Repair Disk on the hard drive (see
Using Disk Utility and fsck). If repairs are reported, repeat Repair Disk until no problems are found. If DU is unable to repair the drive,
DiskWarrior can often make directory repairs that DU cannot.