GIS software works by reading data encoded with geographic information (e.g, longitude, latitude, elevation) and renders it as a map. Common file types that QGIS can read are:
DEM (Digital Elevation Model) - contains geo-referenced elevation data
GeoTIFF - contains geo-referenced elevation data (note - not all TIF files are geo-referenced)
KML - a mark-up language kind of like XML that stores vectors, is commonly used by Google Earth
SHP (Shapefile) - stores geo-referenced vectors, can be a very powerful format as SHP files are linked to database files with additional information on each vector (shape)
1. Obtain Elevaton / Bathymetry data (if desired)
Elevation data is usually found in DEM format, although it can be as a GeoTIFF in some cases. Good sites for elevation and bathymetry data are:
ETOPO1 - Elevation and bathymetry data good for maps covering large areas. GeoTIFF format. The image is downloadable as one (very large) tile so it can be difficult to manipulate in computers with smaller amounts of RAM.
SRTM - Elevation info only that covers 50 deg S to 60 deg N. There are a number resolutions:
SRTM1 - the best resolution, only available for the US
SRTM3 - data files are 1 deg latitude by 1 deg longitude and available for the entire world
SRTM30 - DEM files that cover large parts of the world. A good substitute for relief maps if the ETOPO1 file is too big.
GeoBase - Elevation data in DEM format for Canada at 1:50,000 and 1:250,000 scales.
2. Obtain data for Borders, Roads, Rivers and Other Features
Download the data for the features you want in the map. Borders, roads, railroads, rivers, lakes, parks, city locations, etc. will all have their own data file. Free data can be found at:
Natural Earth - a large selection of data in the public domain that is good for maps that cover larger areas (countries, large provinces and states). Available scales are 1:10m, 1:50m and 1:110m.
GeoBase - Detailed road, hydrology and location names for Canada. Some provinces have also released administrative boundaries.
Government websites (federal, state, provincial, municipal) sometimes have GIS departments that publish free data.
Data formats: This data comes in a variety of formats. I prefer SHP files since they are the only vector file type I've been able to reliably export to SVG format from QGIS.
Scale: It's helpful to have data sets of similar scale. The ETOPO1 elevation data and Natural Earth road and river data go well together because they have a similar scale (1:10m + ). On the other hand, if you paired Natural Earth river data at 1:10m scale with 1:250,000 elevation data, it won't look good because the river won't follow the more detailed land contours found in the 1:250,000 scale data.