I have a list of roughly 500 addresses that I'd like to plot on a map either as a point layer or as a kml/placemarks. The addresses are in form 123 QGis Street, Province, Canada, A1A 1A1
The quickest solution I would suggest is use the online website Batch geocode and try to get your data in a spreadsheet format the site is willing to accept. Batch geo gives the option to export as a kml file.
Alternatively you can simply create your own kml file and specify your string within the address tag. When you load up the kml file into Google Earth it will attempt to geocode those points. Also their is a suite created by Bruce Ralston from the University of Tennessee that does essentially the same thing, kml geocode.
There are various ways you can geocode (either online or with a desktop GIS suite), and if you have access to a street centerline file or a parcel dataset these may be better options than using online geocoders.
I'll post the other links in a comment, I'm limited to one hyperlink since it is my first response.
Using http://www.hamstermap.com is faster as you can copy / paste your addresses in any format, as long as you keep one address per line.
After you are finished with geocoding, you can grab the coordinates and display them using Quick Map.