Creating a small web-mapping/map-tiling service

For a simple way to do this starting with QGIS you could use QGIS Mapserver which can serve maps that you design using the normal QGIS interface. Alternatively you might want to go with GeoServer which is Java based and probably easier to install. Since both programs serve maps using open standards if you start with one and need to switch later there is no need to change the client.

Once you have a system set up to serve out WMS maps you'll want a client front end. I'd recommend OpenLayers as it is pretty simple to get started with and easily expandable. It handles WMS, WMST and OSM tiles with no problems.

Ultimately you may need to move to tiles for your WMS layers (say you start getting more than a 50-100 requests per minute on reasonable hardware) then you'll want to look at putting a tile cache in front of the map server. If you used GeoServer then you can use GeoWebCache which is built in or you could use TileCache.

being able to show categorized polygons in a thematic map (- if possible, it would be nice to get popups or to be able to retrieve attribute information - but that's highly optional)

I would prefer to do most work (styling, etc) in QGIS

OSM as base map would be perfectly fine

All this can be done within QGIS and the ogr2layers plugin. The workflow is simple:

1. Style your data in QGIS. Use the old symbology as I had issues with the New Symbology when using the ogr2layers plugin.

2. Launch the ogr2layers plugin and define the openlayers settings (such as map size, map controls, basemap, etc). This will create a directory containing the index.html and your data layers converted as geojson files.

3. Upload the directory into the webserver.

Note that this is only for simple webmap. For creating custom basemaps and other webmapping features, check out iant and Peter's answers.

Another option is TileMill -- it supports tiling, interaction and cartography in an easy to use web-based interface, including style definitions in a proto-CSS language called cascadenik. Using TileMill, you can crank out mbtiles files which can be consumed with something like TileStream. That said, there are still some tricks with deployment of the mapped outputs, but this would give you a nice platform for generating high quality tiles.