The best way (I define best as with the most people reached and converted to users) is an expensive marketing campaign.
But OSS-projects usually don't have much money. But there are some, that can raise a lot of money. The Mozilla Foundation did this and used money to print big advertisements in newspapers in different countries. It's hard to measure how much that helped Firefox to reach todays popularity, but it surely had some impact.
The most common way to advertise OSS is through social media. This is relatively cheap (it takes the time of a volunteer or a paid community manager) and can reach a lot of people with resending of messages.
The basics to help also any other form of advertising is a good informative website. Other advertisement can send visitors to the site, so the site must contain the information and download for the software.
Much other forms of advertising exist, that are used from time to time:
- presenting the software on conferences
- create merchandise
- use a popular project hosting platform (being on one alone helps to get hits)
- register in software catalogs
For all advertisement it is helpful to keep in mind which target group the software has.
For the question if advertising with Open Source helps: again it depends on your target group. Firefox for example doesn't concentrate on being open source, it focuses on being without charge. In other communities it might be helpful to focus on being open source.