you will need:
+ gameplay demonstration (all vital and unique gameplay features need to be visible/playable/rateable here)
+ cut out all videos and other time consuming junk
+ game design document (2 versions: a=presentation, portfolio like and b=detailed one, including timetables, milestones, ideas of the deal you want and so forth)
+ company description, contact and all legal issues as well as a short portfolio)
+ team member description (manpower, who does what, replecements and plan B set ups)
+ web site
how to contact:
+send them a short mail with a link to your work
+wait till they contact you
+if they are interested (and even if not
) send them the small presentation portfolio (demo + gamedesign a + basic info about you) .... nda might need to be signed befrore that
+after a few days have passed call them and ask if they got the package. try to get an invitation into the house. Here the dual demo strategy pays off: you remember that you have sent a basic demo that only demostrates your gameplay well. The one you can present now also includes more details and a remarkable gain of quality in art, gameplay and so forth.
+ after that you will probably spend the next month sending contracts back and forth till they are signed.
the thing most publishers are worried about are unfinished projects. Thats why they dont trust indies that much.
Your chance is to show them that your game will be finished in timeline (always add 30% more to the timetable then you thinkg you need), it has a reasonable price and you know your target audience.
say yes to small changes, say no to big ones. its a giving and taking game. you give and they take
always and under all circumstances make sure that you
a.) get a ratio for every sold unit
b.) determine costs in your contract (you will get payed for example 2bucks a unit after they returned their costs....write down exactly what these costs are!!!)
c.) try to get back the license/rights for your game as soon as possible
the bottom line is that if they think they can make money with you they will arrange a deal.
good luck
cheers