How soon does a street added to OSM appear on public maps?

The data is available to all users as soon as you have saved it/uploaded it (terminology depends on your editor). Once it is in the main database, it is usually a couple of minutes before it is available in the database used to produce the standard tiles that you see on the www.openstreetmap.org homepage. How long it takes after that for you to see the changes is usually down to older tiles in a cache somwhere, often locally. In many browsers shift and refresh together will clear the local cache (well, when I say many, I think at least Firefox and newer Opera versions).

1. How fast is it on the public map?
   -- @EdLoach already answered this - again in short: the standard map (remember: this is only one use [out of many uses] of OSM data!) on http://www.openstreetmap.org is usually and currently (last months at least) updated very fast (below ten minutes). Other maps/services made of OSM data may take much longer (a week or month is usual) - that depends on the service and you may see it in a service's FAQ.
2. And how fast are the changes I propose on the public map?
   -- See 1.
3. How is the procedure when i have proposed changes?
   -- there is no procedure, there are no proposed changes. You edit the live OSM database.
4. Do the original adder have to accept the changes?
   -- No, there is no "accept" process, see 3.

Please also see other questions and answers about how long the map update takes. Note that the update time span may change over the years. Also see the related question about update speed on our FAQ page in the docu wiki.