Usually, a designer will begin by creating a "sell sheet". This is a page of pictures and information, spruiking and explaining the game.
If it's convenient, you can attend a game or game design convention, and show your game to a publisher there. If they like it, you give them the sell sheet.
I'm in Australia, so this wasn't an option for me. Also, I don't believe it's necessary.
The standard approach is just to email the publisher (or fill out the form on their website.) You send them your sell sheet, or just put images and text in the email. If they like the look of the game, they'll typically ask you to send them a physical copy by mail, or play it with them on Tabletop Simulator.
Even a small publisher will receive around three game proposals per day. They won't even look at most of them. Publishers will usually ignore your proposal. Sometimes, they will reply, stating that they're not interested. After a week or so, you propose to another company. You don't want too many proposals going concurrently, as you may get multiple interested publishers. You also don't want to burn through your list of publishers too quickly, because you'll improve your proposal skills, and the appeal of your game, during this proposal period.
No kind of pleading or story improves your chances. In fact, my simplest email was the successful one.
Here's my entire proposal email, that led to Roxley viewing my video, and then publishing Radlands (then called Delta Six):
I'm Daniel Piechnick.
[one or two lines of personal profile]
GAME PROPOSAL
Name: Delta Six
Theme: Futuristic
Play
style: Strategy
Players: 2
Duration: 20-30m
Components: 84 cards
Weight: Medium-light
Gameplay video: [url of video on youtube]
This is the kind of proposal someone makes when they don't have to explain or make excuses for anything. And it works. Just remember that the more you write, the less good it is. If you have a published game, or something relevant and notable to say about yourself, include it at the top.
Make a video of your game.
When you propose your game, nothing can compete with a video. You can show the quality of your gameplay, and give the publisher an insight into your game almost as good as they could get from actually playing it. Companies are increasingly requiring video-based submissions. It's so much more effective, and so much easier for the publisher.
You don't need to make a high-quality video. Use your phone camera, or record your computer screen. You talk, and give commentary as you play and explain the game. Don't bother trying to coordinate with a real opponent. Just play everyone's hand.
My successful proposal video for Radlands contains art I don't have copyright for, so I can't show it to you.
I recorded myself playing the game on Tabletop Simulator.
Get to the gameplay at light-speed. Some viewers will literally leave the video within seconds. This publisher got three other game proposals today.
Do not explain the rules. Just start doing stuff, and narrating. Add in minimal snippets of rules explanation only to explain what you're doing. Do not stop playing, in order to explain things.
Obviously do not explain the setup.
Do not explain maintenance. If you have to discard or replenish things, or get income, that's obvious. Just do it.
Your first move should be something that is typical of the game, not some weird combo or action type. Do not play optimally.
Weave in strategy musings more and more, once the rules are established.
Make the video 10-15 minutes long, and no more. Just play a few turns, and leave the viewer interested.
Don't bother stacking the deck. My random on-camera games were far better than ones I tried to "stack" off-camera. If the game goes bad during a recording, just start again.
Upload your video as a private YouTube video. This way, you can see who has viewed it, because you can see the viewer's country/state. You can also see how long they watched the video for.
If a company watches your video, and they don't get back to you soon thereafter, they're not interested, and you can move on.
After my proposal video piqued the curiosity of Gavan, the boss of Roxley games, he got back to me almost instantly, and asked if he could play my game on Tabletop Simulator.
We played it the following day. I let him save the game. He went off, and played it with one of his colleagues. They played it twice, and wanted to play again.
The following day, Gavan got back to me, and offered to publish the game.