First of all, when contacting a publisher, you have to make sure you show them you mean business. You're not looking for someone to play your game, you're looking for a business partner. I don't know much about your project, but I recommend that you do various things before you contact a publisher.
First, build a website that looks professional. On that website, you have to tell what the games is, it's key features, show a couple of screenshots and post some gameplay footage. No demos or anything like that, just pics and vids.
Second, build a business plan. Know how much time it'll take to finish the game, how many people will work on it and how much it'll cost. Also, have a good idea of when you want to release the game, what territories you are aiming for and how you want to get paid. Are you getting some funding from government or external investors? You have to tell an interested publisher these things so that they know what they are expecting. But before we get further in that topic, let's talk about the approach a bit.
When you approach a publisher, first of all, never shoot randomly. You have to know what kind of publisher you are looking for and what is your game's honest potential. Don't bother shooting your gore FPS game at some publisher that focuses on kids game unless someone in the company has told you that they decided to head this way. Finding a publisher is like finding a date: if you take whatever lies around you might not be statisfied; If you take a bit more time to search, you'll find someone with similar interest. Secondly, know who you are talking to. Search their website(s) or call them to know who is responsible with game submissions. Get his/her name, email and if possible phone number(s). Then you can prepare your approach. Remember, You have to put the publisher in confidence when approaching it, making sure it doesn't think you're just some guy like a million others but a pro and serious business partner.
When you do your approach, say general but sturdy facts like: "I'm head of team X and we are working on our (first/second/third etc...) title named X. It is currently at STATE_OF_GAME_HERE (like full playable demo, tech demo, alpha, beta, gold) stage and we are looking to secure a publishing deal." This'll tell how far in the project you are which will give a good idea to the publisher how much money it'll need to invest. You can also tell your team's state if it helps, like "we're a bunch of leads with 10+ years of xp in the industry and we decided to make a game together". Whatever fact you have that will tell the publisher you are serious business partners will help.
In your approach, always tell why you are approaching the publisher in particular. Saying "We believe that you would be interested in our game because of X and X reasons because it fits with your current games, such as PUBLISHERGAME_A and PUBLISHERGAME_B" means that you know what kind of game they publish and understand their publishing direction. If you don't show that, the publisher will feel like you're just spamming.
Always tell the publisher that you can provide extra info about the game on demand. Don't show it unless it asks. Of course this means that you must make sure you have design documents, pitch/high concept documents and if possible a working demo at hand so that you can show something if the publisher is interested. Side notes about demos: never release a playable demo before finding a publisher. Most publishers are very happy to know that they have exclusivity. The second a gameplay mechanic can be played, it can get stolen. You can show parts of the idea in vids, but do not allow the public to play it before you get a contract. And, speaking of contract, make sure you specify if you can release a demo and when you can start doing so.
Earlier, I talked about business plans and time schedules. Well, if the publisher ever wants to get serious with you, that's when you need to tell him what you want in the business relationship. The details vary from one game plateform to another but in general, knowing how much it'll cost to finish, how many copies is gonna be made and how much they'll pay you (and using what method) are the key issues to discuss. It's wise to never sign the first deal. Especialy when dealing for the first time with a publisher. It is usual to see new devs getting exploited by publishers. It's not a bad behavior from their sides, you're doing some very serious and high business with them, it's just that the new guys just sign whatever paper the publishers shove under their noses. If you ever get an offer, read it and make sure you understand it. Counter offer with something similar but that pulls the blanket more on your side and see how they react. Then, keep dealing until you both are satisfied with the terms. Try to remain cool headed even when dealing with big numbers, wich is very usual when talking about games. A 250 000$ offer for a game might look tasty but when you think about it, it's pretty bitter. You have to pay for taxes, an even share to all the team, office suplies, buy licenses for your hardware and software (specialy if you are using pirates or working on consoles), find a place to work, pay the rent and in some cases pay for some advertisement and box artworks. Sure you can cut back on many things but 250 000$ is spent real fast in the world of video games. Plus, you'll need to put some on the side if you ever want to make another game.
Well, I hope this helps a bit. There are many things to look at when going in the big leagues with a game and it ain't always easy. But, don't give up, it is quite possible to succeed, you just need to have the guts and a good plan of action.