Shapefiles and OpenStreetMap data do not overlap in QGIS?
What we really have to find out here are the projections of your input data.
City data
The Shapefile comes with a .prj file that is perfectly interpreted by QGIS. Don't change the layer settings!
OSM data
If you are using OSM vector data, they are in WGS84 Geographic coordinates (EPSG:4326). Only the raster tiles are in Web Mercator (EPSG:900913).
Open Street Style data
If QGIS recognized the .prj content, leave it that way.
Finally, chose a project coordinate system (I'd suggest the UTM one) and activate on-the-fly reprojection as @Mike_Toews already explained.
You need to reproject the different layers to the same projection 'on the fly'. Go to:
Settings > Project Properties... > Coordinate Reference System (CRS)
and check on Enable 'on the fly' CRS transformation