New roads can be recorded by turning on "Record new Roads" mode on your client. Read the user manual for your type of client how to do this: iPhone / Android / Windows Mobile / Windows Phone
Make sure you only enable this mode when you are driving on a road that doesn't exist, or at least only for a very short time on an existing road. It is possible that Waze may record a new segment for an existing road if the GPS accuracy is off by enough that Waze may believe you are on a new road. It is OK to drive for a short while on existing roads while recording so that the intersection with the new road gets accurately recorded.
The recorded road will appear on the map after a certain amount of time.