I'm just starting out as a freelance developer and I've reached out to clients who were referred to me and they don't have work ready for me yet. How often would it be appropriate to follow-up with these clients to let them know that I am available and interested in work without seeming too pushy?
This is a tough questions and it really varies from a client to a client.
I would try once a month for a couple of months (let's say 3). Then move this to every 2 months. This is in case of a remote clients.
Try to get friendly with some clients and ask then to contact you in case of any job, even in case of tasks only.
I am doing it this way. Sometimes they don't reply at all, some times they tell me "get back to me in a couple of weeks". If they stop replying, then I'd wait for 6 months - till they forget about you :). Occasionally you'll have to dismiss some clients.
As with the previous posts, this is difficult to measure as a general rule. So let's look at it from the client's prospective. This will refer to the SPIN selling I mention in this answer, as it applies here a little bit.
You need to show your client that you fill a need, even if they don't know what the need is yet. In my industry (Information Technology), customers tend not to know how to do things quicker (i.e. with scripts or custom programs), or constantly (i.e. scheduling backups, checking logs, etc). I need to show them how the problems of not having me can have negative effects on the business. That is the Situation. The Problem is that they are not using me, and therefore, losing money (Implication). The Needs Payoff is when I come in, fix things up, make everything smoother then ever, and they get to work properly, and more efficiently.
As for contacting them, unless they are expecting your call at the time, or you know them on a personal level, they will likely see calls as simple spam. Telephone marketing does not usually work on most professionals, in my experience (both selling myself as a freelancer, and as a salesman for a technology company). The two best forms of contacting a client are in person, or via email. Email is easy to disregard as spam, but is also much easier to deal with, and you can get away with sending in a promotion once a month, without getting on people's nerves.
If you can get into the office of the person who is making the decision, you are over halfway there! That is when you can explain how your services will improve their business, make everyone more efficient, or whatever you may provide as a service. Sometimes you will have a "gatekeeper" (aka the secretary) who will always deny you, but that is when you can pull out the business card, and trade with the manager's email and full name on the card. You can then tell him/her that you will email the boss in a few days with an offer for your services, and that you look forward to talking with them in the near future. Always have a smile on your face, and do not become the pushy salesperson!