The free resources at openstreetmap.org are staggering in their scope and generosity. If you so wish, you can help the openstreetmap community build better maps by editing or otherwise contributing to their maps. The best place to start is their Beginners' Guide which outlines a few of the ways you can help.
The easiest way to start is with the built-in editor in the openstreetmap website. You don't need to download any extra software, you just need to look for the "Edit" tab at the top of the map. You do need to register though, and you do need a valid email address for them to send your confirmation code. Once that's done though, you can get started immediately with naming roads, adding points of interest and so on. There is a bit of a learning curve, and it's not always intuitive to use, so make sure you practice using the "Play" mode before you make a mess of someone else's carefully-created data!
Once you've practiced, and got the hang of the tools, you can go to the real "Edit" mode and start editing the data for real. Accuracy is more important than speed, however. It also requires a bit of patience as the data gets downloaded and the tool can lock up occasionally, so make sure you save often. One tip is to zoom in tightly to the area you're interested in editing before you go into the edit mode, to reduce the amount of data which has to be downloaded. It can still crash the browser though so if you're doing anything more than a quick edit or two you may want to look at JOSM (see below) which provides a more robust tool for frequent edits.
In any case it does take some time (maybe a few days, maybe longer) for the changes to become "live" in openstreetmap maps. But once they are, they become available to everyone thanks to you! And even better, next time you make an extract from OSM for your GPS receiver, it'll have your edits in for you!
JOSM (Java OSM editor) is a standalone java application, rather than an in-browser tool, so it takes a bit more effort to get it going - but not much more than a download of the jar file. You should have at least java 1.5 installed already before you start.
It's a powerful tool, with lots of options, and it's not particularly friendly when you start it for the first time. But if you select "download from OSM" and use the "find" tool (not the map window) to select a town you're interested in (preferably a small town!) then it'll go and download the data for you and show it on a black background. Make sure you "zoom to data" to see anything. But even then the writing is tiny for some reason, and barely readable. Still, if you get round the slightly strange right-click-and-drag to zoom, left-click-and-drag to select idea, then you can select points and ways and see their details. Sadly you can't see the history of items yet though.
Obviously the whole point of JOSM is to edit the data and upload it back to OSM to be incorporated into the maps, and this is best done using GPS tracks which you have recorded yourself. I originally thought that the map was generated directly from the GPS data, but I was wrong - effectively the buildings and roads and other nodes are drawn "on top" of the GPS tracks, using them as a guide but generally simplifying the route and using much fewer points. Then you can add tags to the objects to give road names, specify whether it's a footpath or a motorway and so on.
There seem to be two main ways of using GPS tracks. The first is to "upload" your track to openstreetmap, which makes it available for anyone to see and use. In fact, you can just submit your tracks and leave it at that, and maybe someone else will use your data to update the map. But that sounds a bit optimistic to me, and you don't get to see your data immediately in the map. Plus, there have been concerns raised about the privacy aspects of uploading your GPS tracks in this public way - if you include the timestamps (as openstreetmap insists you must) then it's a permanent record of exactly where you were at that exact time. If you upload lots of tracks then making all this information public might become a worry. In fact, this was precisely the reason why GpsPrune got a new function to add a time offset to all the timestamps in your track, to prevent people from seeing exactly where you were on which day at what time.
But there's another way of using your tracks, which doesn't involve uploading them to openstreetmap at all (as far as I can tell, anyway) - you can just load a GPX track from your file system into JOSM, which shows it as a (rather too faint) dotted line. Then you can download from OSM the map data for this area and view it together with your track, and edit the map objects accordingly. Finally, you can upload the changes to OSM, but this only uploads the nodes you have added or edited, at least it doesn't appear to upload your GPS track.
Again, it takes a while for the renderings to get done so that your map edits appear in the real openstreetmap, and it may be that your edits appear at the overview zoom levels before they appear in the more detailed zoom levels. But it's quite cool to see your changes finally incorporated in the map! And especially when you then do another extract and they appear on your GPS screen!
So the basic recipe for adding elements to openstreetmap using JOSM is as follows:
One possible complication to this recipe can occur when OSM changes its interface for downloading and uploading data. In this case unfortunately the OSM server isn't clever enough to still use the old interface if required, and JOSM client isn't clever enough to give any meaningful message that the interface is no longer supported, so all you get is a confusing HTTP 403 error.
The solution is straightforward, if you know it - just download the latest version of the JOSM jar file and overwrite your previous version. Then restart JOSM and your HTTP 403 errors should be gone.