Press releases are important for getting widespread attention. If your university is anything like U.S. universities, then they will have a PR office that can help issue press releases. Of course they won't do it unless they feel there's a plausible story, but if they do then they can be extremely helpful. Some top journals (such as Science and Nature) also try to pitch stories to the press, with embargoed access to papers before publication.
It's absolutely critical to think about timing. At least in the U.S., science journalists care a lot about newsworthiness. If they are writing about a single paper, then they generally want the story to come out when the paper is published, rather than a month later. (In some cases, they would lose interest even a week later. The only way they will maintain sustained interest over time is if the story is extremely important.) If they are writing about a larger trend, then they want their story to appear while the trend is still new and surprising, rather than being a retrospective account. This is radically different from how scientists typically think about public communication. We'd like to see stories that teach the public something valuable, regardless of how fresh and newsworthy the topic is, but journalists lose interest incredibly quickly.
Is it a faux pas to write an enquiry directly to a magazine journalist who has previously covered research in a related area?
It usually is. My understanding is that science writers get a lot of unsolicited requests to write articles on the requester's work, and having to deal with this does not make them happy. Instead, you can build contacts in other, more constructive ways. One is to offer tips for hot stories on other people's work. Of course you should do this exceedingly sparingly, but if there's a major breakthrough in your field that is very recent and exciting and has not yet had any news stories on it, then that could be a useful tip. Another way to get your name out there is by being interviewed. Your university PR office may be able to connect you with journalists as an expert they could interview regarding stories in your field. It wouldn't be about your work, but it would get you some attention, and if you impress the journalists they are more likely to remember you and pay attention to your work in the future.
Having a high-profile science blog is also a good way to attract attention from journalists, since it establishes you as an expert who can communicate well with the public (which is ideal for getting good quotes).
If a press release is the way to go, exactly how and where should it be posted or submitted?
You shouldn't do this yourself, since it would look tacky. If your university or publisher is willing to do it, then they will know how, so you should ask them. (But don't bother asking the publisher unless it's a fancy journal that is used to doing this.)