What you will be doing is known in the fund-raising business as "cold contacting." This means that your "target" company won't have known that you'll be contacting it, and won't have been primed to hear your message. A 1% response rate is considered normal. You should be able to do better than that.
In a sense all target companies will be slightly primed to hear about Linux due to the remarkable amount of publicity it's been getting of late. In that respect your contact won't be completely cold. That's good.
The first thing to do is to identify someone in the company to contact. It's always best (if possible) to identify an actual individual rather than a job title. Depending on the size of the company and its organizational structure, your best bet is the head of program development. If that isn't a possibility, try for the head of whatever technical section the company may have. If that isn't possible, read over whatever bios might be available in the "about the company" section of the company's web site (they almost all have something like this) and pick the person who seems most likely to be intrigued by Linux and to become an internal advocate for a Linux port. Finally, if none of the above things works try contacting the head of the company. Incidentally, it won't hurt to contact more than one person in the company if your bio research shows somebody other than the head of program development as the most likely person to be interested.
Your initial contact should probably be via email. First, email usually goes directly to the person addressed rather than being filtered through various layers of the organization as postal mail and telephone calls are. Second, with email everyone starts equal. Physical presentation and elocution don't enter into the contact, so the logic of the message may be more apparent.
The subject of your message should be understated. "Make Millions Easily!" will just get your message deleted as spam. Try something like "A good new market for your programs," or "An overlooked market for your software."
The first sentence in your message should probably be a conditional apology for sending the message to the wrong person if the person receiving it is the wrong person. The next sentence should request that the message be forwarded to the right person and that the person's email address be sent back to you for future contacts. This has a few effects. The apology establishes that you're not a know-it-all and that you are polite. The request reinforces the politeness and quietly lets it be known that this won't be a one-time contact. That's important. It's a lot easier to blow off a message if you don't think you'll ever hear from the writer again.
That brings up another point. If things work out right, you won't be making just a one-time contact with this company. You will be signing up to be an outside contact for them, a source of information about things Linux. As such, there are some guidelines to follow in all your contacts. Be polite. Be patient. Be truthful. Be helpful. Stay apart from internal politics.
Be polite means responding civilly to all messages, even if you consider them insulting or moronic. Remember, "A soft answer turneth away wrath." Besides, it's just possible that you may have misunderstood the message. Asking for a restatement of the message to clear up its meaning can't hurt.
Be patient means answering what you consider obvious questions calmly and clearly, and answering them as many times as necessary. Email isn't real-time; you can take a jog around to block to cool down before answering yet another, "But doesn't a Linux port mean we'd be expected to give our products away?" message.
Be truthful means answering each question to the best of your ability, and saying "I don't know" when that's the correct answer. However, "I don't know" is only the first part of that answer; "but I'll find out and get back to you" is the rest of it.
Be helpful means going beyond just answering the immediate question and trying to address the reasons the question was asked. For example, one company asked me how it could publicize the existence of a Linux port if it did one. I mentioned the standard places (comp.os.linux.announce, Linux Weekly News, Freshmeat, Slashdot, Linux Journal). Then I brought the question up in the seul-dev-apps mailing list. The discussion there eventually started the development of the lu-news system.
Stay apart from internal politics means keeping a little distance between yourself and your company contact. However friendly your exchanges are, your role shouldn't be one of confidante but one of outside expert and advocate. You won't force the company into supporting Linux. You can only make sure they know about the opportunity and help them find the best way to take advantage of it.
You should probably be prepared to answer questions about why no one else in the target company's market niche is developing for Linux (if that's indeed the case), and what capabilities are available in Linux, such as multimedia. Are the available media players exploitable commercially? Do they run efficiently? You might also make the point that a port to Linux of a graphical program will mean a port to the X Window System and will mean that the program is much easier to port to any other OS that uses X, such as Solaris, AIX, or HPUX.
Andrew Mayhew brought up this point to me, and it makes a lot of sense:
It has been my (albeit limited) experience that structuring the email/letter sent to companies with the idea that I or one of my clients is actually interested in their product at the beginning (or as closely as reasonable) of the document gets more results. Now, this is only really applicable is you mean it.