Why haven't my changes appeared on the map?

There are kind of two parts to the answer to your question.

For one, the data you add to the database is used in many different applications. For example for rendering map tiles, for using on your phone, for routing, in your Garmin devices, for your satnav, for searching, to make art work, in flight simulators and many more applications. Each of these applications have their own separate update schedule. For some applications it might only take minutes for the update to trickle through, other applications might only update every month or so. However, due to this huge diversity of uses of the data, your data will be immediately useful for some.

The other part of your question is how often does the "mapnik" map view on openstreetmap.org update. It should be updated within a few minutes, but currently the rendering server is fairly overloaded, so it might take longer and you might have to view that area of the map multiple times for it to trigger the updating process. For a more detailed explanation of the process and how it works, have a look at this answer.

It does take some time for edits to appear on the map. Sometimes only a day or so, sometimes much longer. Sometimes it appears on some layers or magnifications but not others for longer. The different layers have to be processed or rendered but I don't know the process. I have found it a problem as I've been trying to fix boundaries or polygons of address areas and I don't know if I've fixed them for even longer.

apmon's answer already explains fairly well how the rendering works.

As an addition:

• The Wiki gives further details on the rendering process: http://wiki.openstreetmap.org/wiki/Slippy_Map
• You can force a re-render of a tile by loading just the tile image (e.g. in Firefox: Context menu / View image), then appending /dirty to the URL (e.g. http://tile.openstreetmap.org/7/63/42.png -> http://tile.openstreetmap.org/7/63/42.png/dirty).
• The rendering only refers to the image display. The search box is powered by Nominatim, which updates on its own schedule. Just in case you are wondering why e.g. newly created/named streets are not found by the search.