I am asking particularly about software and IT services company, but I think question can be answered generally as same dilemma is shared by entrepreneurs of different industries.
Basically you are going to have to do something to convince people they should use your software/service. You do not state what specifically you are offering, so I will address a couple of cases.
If you are offering contract programming by the hour and are looking for your first customer, you may have to simply offer someone a deal that is too good to pass up; you need to prove yourself. Start with a small project so that you will not loose your shirt and find a client that will give you the job with the offer that they don't need to pay you until the job is done and they are happy with it. They should also agree before you start that will be willing to serve as a reference (assuming you do a good job) Once you have one project under your belt than number two will be much easier to get.
If you are trying to sell a software product, offer a free trial. This is common in the software industry. Put it on a website and allow people to register and download a time limited version.
For software as a service (SaaS) offer a similar free trial.
I am in the mist of doing this exact thing. First, I started with Google AdWords which was an expensive bust then I read a few blogs on start ups that pointed me in the direction of starting small and building from there. Define who your target market is and talk to them. Find out what they want and advertise your service to them as well as be ready to make adjustments. So, making connections with people and being flexible is the key.
You need to bring relevant traffic to your web site by means of adwords or yahoo marketing. There are many aspect of such a move including design of landing page, design of web site. You will need to speak to a really good web designer or post a job on Elance.com
Micro site also work very well. If you have a focused product or service you can create a micro site exclusively for that service / product free from all clutter of a corporate web site.