I think the most important thing is (hope I translate it well) mouth-to-mouth. Make good things and people start talking about it with others. So you could do some cheap or free jobs in the beginning so you get a portfolio and your network will grow. When people are happy with what you have made for them, they will tell their friends about it. And if your network grows to slow, you could also try to advertise somewhere or SEO your website that good that it will be on the first page with relevant google results, but I think a good network will help you more.
I’m with Edwin. Do good work and work will find you. Very rarely do I ever get truly "random" work. It always comes from some connection to a previous client or someone who has seen other things I’ve done.
That said, I’m not really a true freelancer looking to fill my days with client work. If I was in that position, I would likely have a different story.
You could also stalk the web for websites that’s poorly designed (or just don’t meet any standards at all), then try to contact the owners with an offer. You just got to start somewhere, then you can build up your own network and work will be easier to get.
I’ve also considered working as a freelance designer – with a strong focus on usability and accessibility – but since I work for a website at the moment (Norwegian Schoolnet), I get somewhat tired of being at the computer in my spare time.
I have gone as far as making PSD mockups in my spare time and showing it to people I want to make a site for. that really impresses them.
If you have an iphone keep your portfolio on it. Its nice to pick up clients while youre at the club by pulling your digital folio from your coat pocket.
If you do good work don’t under-charge. You don’t want bargain bin scraper clients, they are the worst. If you get a client that says, "I’m talking to another designer and he says he can do everything youre offering for [much less price here]". Don’t go down on your price. You say "Well thank you very much for your time I appreciate your consideration but [price] is my best offer."
If you offer a fair price and good work there is no reason to undercut yourself. I’m still learning my lessons though.
Word of mouth if great.
When speaking to people about your work always be confident and know what youre talking about. If you don’t know something don’t talk about it. My sister’s husband drives me crazy when he blabs on about things he knows nothing about like "only special motherboards with built in mounts for water cooling can be water cooled." or "XBOX 360 is techinically superior to the PS3".
Potential customers will feel the same way if you say something thats clearly not true.