I've managed to get something working, but it's not as good as I hoped and there may be a better way.
Add OSM
First I added the OpenLayers plugin and selected Plugins -> OpenLayers Plugin -> Add OpenStreetMap layer.
Import points
Next I created a CSV of my points like this:
LATITUDE,LONGITUDE,NAME
20.201389,14.965278,Name1
20.187278,14.97020,Name2
Then I imported it following these instructions, but with a comma delimiter, then zoomed and panned as needed.
Labels
Then in the layers panel I selected my points layer, I selected Layer -> Labelling, ticked "Label this layer with" and selected "NAME".
Print
Next I followed these instructions, starting from "click on the ‘New Print Composer’ button", adding just the things I needed and changing to portrait. I then exported as image and saved as PNG.
Results
This gave me a correctly sized (2480x3507) PNG. However, I found that often it would export an image with some white tiles. More often it would export with my points in the wrong places on the map. After retrying and restarting many times, I finally got an image with a complete OSM background and the points in the correct places. I still need to test a printout, but I think the OSM background is much more pixelated when compared with the smooth markers and labels, so perhaps there's a better way of doing it.