1)
You need to bring them a demo of your title, then they will make the decision as to whether or not they want to market you. Similar to a record deal. You need to have something they want, you just do not pay them to market/publish your game/software.
2)
It depends on the publisher, but I would think anywhere from 30% and up. Depending on whether or not they think it will be a big hit or not. Otherwise, as in one, they may just make something unreal, and hope you do not persue it any further.
You also need to pay for contracts to sell the game at various locations and online vendors, this costs money too, and is included with the publishing fees.
3)
No, not normally, the game is your companies, and yours alone until it is ready for production (past beta and ready to rollout). You, initially, have to pay, more often than not, to have the game marketed, until they feel it will be a hit and sell. Again, it's about money, they need to make moeny on the deal, not lose it.
4)
Of course, nothing is for free. Just as if you wanted to list something in the newspaper, you have to pay. Same applies here. Normally there is a % that you must pay upfront, and the rest is paid after release.
As others have mentioned, even with the most simplistic of games/software, it takes time, and again, you need an engine, or you will have to build one from scratch, and with anything, that will take a huge amount of time. I mean, think of how long ID worked on the Doom 3 engine, and that was still designed from the Q3 barebones, so there was atleast a template (to my knowledge it wasn't completely re-written). And think of how many programmers they have working on it at any given time.
If you are serious, then I would look for people who have experience, or go with a 3rd party marketing company (freelance), they will atleast get you started, and take care of some of the necessary paperwork, but there are still selling contracts and other legalities which would have to be taken care of, and they are not cheap.
Later,
Oz
Rig:
Athlon 64 X2 7750 Kuma @ 3360 Ghz @ 1.475V (14.5x223)
(NB: 2240, HT: 2015)
Gigabyte MA-790X-UD4P
Sparkle GeForce 9800 GTX+ (755core, 1350 mem)
Onboard sound (yuck)
4GBs Mushkin DDR800 (6/6/6/18/24 @ 928mhz)
2x74GBs RAID 0
2xWD 1TB HD RAID 1
Plexter DVD Burner
Rosewill 530W