It is usually far easier to get companies to provide their services than cold hard cash. Take a look in the yellow pages and look at local companies and get in contact with them. You can approach larger companies however you may find that they get asked for sponsorship for various projects all the time.

When approaching a company, be honest about what you are offering them. Don't say that you will get their name on TV as the chances of that these days are minimal to zero at best. If you have a completed robot then take it to them or show pictures. If you don't have a robot have CAD drawings so they can easily visualise what you are planning on building. You can offer to let them borrow the robot to display their products to customers. Displaying the company name on a robot during competitions is usually the standard offer with a mention on websites etc. What benefits does this bring them? Well if you are at a big competition your machine may be viewed by a good few hundred people and other roboteers may want to contact them about their products or services.

Personally I'm not a fan of sponsorship. Two reasons, I don't like my machines covered in other peoples logos and with sponsorship there is an expectation that you will deliver on your promises (hence don't promise the world!).

It can be done but takes a fair bit of work.