List on as many directories etc as possible.
Get it listed on all the paid for ones and possibly even Yahoo. I know it costs but at least these are all links to your site. One way as well.
This could cost well in the region of £1000 maybe a little more.
If your client wants to promote their site without putting aside a decent budget for this, wish them luck.
