How do I change a street name?

1. Zoom in to the area of the map showing the street.
2. Click the 'Edit' button.
3. Once the editor has loaded, click the road and type the correct name in the panel on the left, and press Return.
4. Click 'Save' at the top. Enter a helpful comment explaining what you did. That's it!

Unlike Google Maps, the change will take effect instantly for anyone downloading the data, or within a few minutes for people looking at the maps.

The earlier answers are both correct. What they omit is that if you don't already have an account you will need to sign up to edit the name, and there is a possibility that a single road consists of a number of separate sections in the database in which case you may need to update the name on each of them. You can tell whether that is the case after clicking on the road so see how long a section has been selected.

Are you using the OSM web page at http://www.openstreetmap.org/ ?

If so then you can edit the map directly on that page. Just position yourself at the area showing your street, hover over the "Edit" tab till you get the drop-down menu and select "Edit with Potlatch 2 (in-browser editor)"

This will start the Potlatch editor, where you will be able to click the street and change its name then save your change. That's it.

For more information see Beginners' guide (OSM Wiki).

If you're a hands-on person, any of the highest rated answers here will work amicably; please read the OSM Wiki page about names first. If you're a map consumer more interested in the end result and don't mind waiting, you can try submitting a bug via a Note to get the attention of someone with a deeper interest in cartography.