Welcome, Amy! Nice to have you here.
First of all, it would be best if you could let us know the exact Mac model you are using, and also what OS you are running under.
Secondly, that does seem strange that you would see that message, even though you have more than 94% of your disk space available. (Just out of curiosity, did you get those figures from the "Get Info" option in the File menu while in the Finder?).
Third, what third party applications do you have installed on the drive? That could be somewhat "revealing".
Fourth, after you boot up your Mac, go to the Activity Monitor in the Utilities folder within the Applications folder and launch it. That will give you useful information as to which processes are running. If most of those are due to the OS, then the appearance of the message is still somewhat strange. But, maybe you'll see some processes that are related to applications installed on your machine that could be culprits.
I did a google search of the issue you are having, and here is one link that could be helpful:
http://www.techjaws.com/resolving-the-error-your-startup-disk-is-almost-full-on-mac-os-x/
Some of the suggestions mentioned in that article actually go along with your last question about using applications that can help your mac run smoothly. I am going to offer some suggestions that maybe could help you.
I like to run "mean and clean", which means that I am constantly getting rid of stuff I don't need. One of the things that I do just about everyday is when I run Outlook to check my EMail, I often receive stuff I don't need or want, including spam. So, of course I delete those messages. But deleting them does not actually remove them from my hard drive. (I'll mention below when I get rid of them permanently).
My "arsenal" of maintenance/backup software consists of 3 products:
1. Oynx (free)
2. TechTool Pro (cost $79, I believe)
3. SuperDuper (it does have a "free" mode, but some features are "turned off unless I purchase the "full blown" product)
Once a week, I go through 4 steps for doing maintenance and backing up, for both of my machines. I first run a two step procedure for permanently removing the deleted Outlook EMails. Then, I run the excellent program Oynx (I'd give you the link to download it, but there are different versions depending on what OS you are running). Oynx can do quite a bit of checking your drive (if it is OK, and Smart Status), a few maintenance tasks (checking and re-setting permissions, running Daily, Weekly, and Monthly scripts, etc.), and a number of clean-up tasks (a number of them mentioned in the link I provided above). Oynx, though, does have its limitations regarding disk drive maintenance/repair, etc. Apple's Disk Utility is "OK" for that, but a more robust tool is better.
So, I next run Tech Tool Pro. It contains a number of useful tasks, including a number of disk-related features (Disk Warrior is also an excellent program). After Tech Tool Pro finishes, I then run SuperDuper! to create a bootable clone/backup on an external drive. (I actually run it twice, backing up to two separate external drives).
I have been following this procedure for a number of years, and it keeps my Macs running as "smooth" as possible. But, I also make sure to do some sort of clean up everyday. In this way, I actually do a decent job of managing disk space.