In particular, I’m looking for everything that has toll=yes; this is widely used but not yet supported by the default renderers.
You can do a query to Xapi, instructions here: http://wiki.openstreetmap.org/wiki/Xapi
eg something like this should work:
http://www.informationfreeway.org/api/0.6/*[toll=yes]
(except the forum is breaking the link, just copy and paste it)
That will give you an osm file with everything tagged with toll=yes. You can open it in JOSM to view it, or a text editor etc. Though note for a popular tag it may be a rather large file, so be slow to download and open. edit: just tried it for toll=yes, its a 40MB file. You can also do a Xapi request for a smaller area by specifying a bounding box, see the instructions.
You can also check OSMdoc, it gives you stats for tag usage. eg http://osmdoc.com/en/tag/toll/
Plus it includes XAPI links. Though I think the OSMdoc stats are a few months out of date.
or use JOSM, the OSM-editor. it has geat search-function
wambacher
I like that, but it’s not exactly what I was looking for. Is there any way to overlay toll roads on the map, like one can overlay a relation? Would it be a good idea to create a toll relation?
No - relations are not categories.
And a relation with all toll roads in would be huge, and impractical to do anything with.
If you want an overlay, its quite easy to show an osm file (or other formats) over the top of a slippy map, see http://wiki.openstreetmap.org/wiki/OpenLayers_osm_file_example
For example, see this maxspeed map: http://maxspeed.osm.lab.rfc822.org/
Quite easy, yeah right 
So I should probably stop adding toll=yes because I have no way to view the results and make sure I didn’t make any errors.
Its not too hard, just copy and paste from the Openlayers example, and change a few things so it does what you want.
Or if you think toll tags should be rendered on Mapnik or Osmarender, then you could add a request on http://trac.openstreetmap.org
Or if its mostly for checking while editing, you can change the styles in JOSM to highlight toll roads. I have just made an example here: http://osmalba.org/josm_styles/toll.xml
Download that file, then in JOSM go Edit → Preferences → Map settings (3rd icon down). Choose the “Map paint styles” tab, then click “New” in the “Active styles” section, and browse for where you saved the toll.xml file.
Then restart JOSM, and anything tagged toll=yes or toll=no will be highlighted.
Except for the “Upload both files to webserver” part I could probably figure it out. Really all I’m looking for is the OSM interface but with toll roads highlighted in the way that relations are.
I switched local toll roads to ‘trunk’, based on the page http://wiki.openstreetmap.org/wiki/United_States_roads_tagging comment:
which renders green on Mapnik and Osmarender stylesheets
Um… check the talk page. There’s a lot of dispute over what trunk means in the U.S., but it’s essentially agreed that toll roads built to motorway standards (like the UK’s M6 Toll) should be motorway.
I have added a request on Trac for toll roads to be rendered on Osmarender. You can add comments there if you want: http://trac.openstreetmap.org/ticket/2597