You should never, ever, be paying anything to a publisher for publication. Never let anyone tell you otherwise. On this board we are full supporters of Yog's law - money flows towards the author. Anyone who tells you that you 'have to pay an admin fee' or 'buy a special bonus for publicity' is scamming you and you should therefore avoid.
Are you talking about a novel length story or something shorter? For a full length novel the traditional way is to find a list of agents who handle your sort of story and send it to then in the hope of representation. There are lots of threads in here about that. They will then approach a publisher for you and negotiate a deal in exchange for a 15% cut.
For shorts, you need to look at anthologies, magazines and small press publishers. Duotrope is a good site to use (do a websearch) as it allows you to search for appropriate ones for the stories you have. There are also some publishers who are listed in this forum - check out the paying and non paying market sections. You should also check out the 'Bewares and recommendations' section for any publisher you consider dealing with and look at sites like Preditors and editors and Writers Beware. These have information on publishers and agents and will help you spot any scams.
Once you find an appropriate publisher, you need to check their writers' guidelines. These tell you what they are looking for in terms of format and cover letter and whether they want it sent as an attachment (in what format - usually .rtf), as inline text or sent to them as a physical copy by mail. It is always a good idea to follow any guidelines to the letter as failing to do so can lead to your work being rejected for no other reason than you failed to follow the guidelines. Also, even if it does not get you rejected, the guidelines are usually there to make it easier for the editor to read and assess your work. If they have to mess around installing new software before they can read your story or they find it difficult to read because you did not use an appropriate font, they are going to be less inclined to be generous to you.
If there are no guidelines for format, there are several good sites out there with details of standard manuscript layouts. Usually you are looking at double line spaced, size 12 courier type font, with name, contact details and word count either on the title page or in the header. However, there are variations on this so don't send anything until you read the specific guidelines.
Cover letter is also a varied thing. Usually, you need to mention the name of the story, the word count and give a bit about yourself - a short bio. However, some also require you to give some indication of a publicity plan and a synopsis and other details. Again, check the guidelines for details.
If you are talking about a novel length story then you are in a different ball park for that. Novel cover or query letters are quite adequetly covered in the 'query letter hell' section of this site...
