If you are doing this while maintaining a full-time job (which by the way is a GREAT way to start), make that fact well-known and make it a marketing plus. I did the same thing and after 8 months was making more part-time than full-time. I then left my full-time job after putting about 18-22 hours per week in place.
You also learn the ropes while having insurance and the like. So, regarding how to market it...
I created a small tri-fold (template right in Word) and included text similar to the following:
Weekend & evening consulting at incredible rates.
I provide "xyz" consulting to local companies. If you have needed high-level expertise but do not have enough work to justify a full-time employee and have been put off by the high-fees of other firms, I have a solution for you.
I provide these services during weekends and evenings, apart from my full-time job. Because I am gainfully employed, you do not have to cover any overhead associated with health care or facilities, leaving you with great service at great rates.
The above is just an example of how you could market the service. Your biggest business growth is going to be through personal referrals so do not hesitate to ask for those referrals.
I hope this helps.