1. Passwords MUST NOT be dictionary words.
2. Passwords MUST be over 8 characters.
3. Passwords MUST contain numbers or symbols.
4. Passwords MUST be changed every ???? weeks/months
This all sounds very reasonable. However, some minimal user training may be in order. I'd introduce the users to a few easy ways to satisfy your criteria, such as 1337 and passphrases, whichever makes more sense to each individual. That way, they're less likely to have problems implementing your guidelines or think you too draconian.
While i don't want to become the local BOFH, i do want to enforce good passwords but not make it too 'hard' on the users so they write them down... how often should a password be changed?
You're absolutely right that if you rotate passwords too rapidly, users will become frustrated and confused, or worse, end up sticking their passwords to things via post-it notes. As to exactly what policy to implement here, you're in a much better position to decide, being aware of the political climate of your workplace as well as the sensitivity of the data you will be protecting. I'd say that the more sensitive the data, the more frequent the password cycles. Conversely, less sensitive data doesn't really merit rapid password cycling, since it will cause more problems than it solves. Politically, even if your data is pretty sensitive in nature, your boss may trump you on that front. These are all things you must weigh carefully, but I'd say as a general rule you should cycle your passwords no quicker than 2 months and and no longer than 6. Also, user accounts should be locked and/or password changed immediately once they've left employ, even if the data is left around for a while.
I don't think it will be necessary to lock user accounts (until i unlock them) if they get there password wrong X times, i think it might be a good idea to lock accounts for 1 minute every time they get there password wrong after getting it wrong 5 times within 10 minutes! or some variant, ether way it would make a brute force attack (or even a dictionary attack) next to impossible while at the same time it shouldn't affect users too much (if at all)... how would i go about implementing this?
You can set these policies and enforce them with PAM, built right into modern Linux and UNIX systems. It's actually quite easy to implement once you have an idea of what you want to do, see the PAM-Linux docs for more info:
The Linux-PAM System Administrators' Guide - anti-trend.homelinux.org
Also, I've mentioned this already but you can use DenyHosts to further harden SSH against DOS and strong-arm cracking attempts from only certain networks (e.g. public ones), whitelisting others (e.g. private networks). It is a simple script which uses your system's TCPWrapper facility to automatically deny hosts for a predetermined amount of time based on abuse patterns, then report this data to you. I highly recommend it if you'll be exposing SSH for public usage -- in a rainstorm of scripted SSH attacks, DenyHosts is a sturdy umbrella.