Since you are on ArcGIS, here it goes..
I suggest starting with learning basics of Network Analyst (further NA). It is impossible to get started preparing the data for network analysis withouth understanding of the basics of the GIS routing and network analysis theory (graphs, edges, junctions, cost, algorithms). Industry: a good place to start is Esri's Help page, a great NA resource here. Science: Geospatial Analysis - 4th Edition - de Smith, Goodchild, Longley (link directly to the NA topic).
After that, you can start building an own network dataset. For everyone who starts with GIS routing in ArcGIS, I always strongly recommend going through this Esri KB tutorial Prepare data for use with the Network Analyst extension. It will guide you through all the details of building a network dataset from scratch.
ArcTutor: To work through the ArcGIS for Desktop tutorials, you need to install the tutorial data from the ArcGIS for Desktop Tutorial Data setup, which is part of the ArcGIS for Desktop installation download or media. If the tutorial data has been installed on your system, look for it in C:\arcgis\ArcTutor (the default installation location). In many cases, you will need write access to that location to perform the tutorial. You are interested in NA exercises, for instance, Exercise 1: Creating a network dataset.
After that, you are ready to build your own network dataset either by processing your own data you already have or by obtaining data from other sources. Here there are some options:
ESRI has a separate product – ESRI StreetMap Premium, which provides access to the street data in SDC format both for North America and Europe and for some other parts of the world. This product can be used in the Network Analyst directly and no data processing is required. Be aware that these network data are for read-only use and no edits to data can be applied. This data product provides the best performance as well as robust functionality, yet the least customization flexibility, because one can only use the street data as it is.
Navteq Navstreets (aka HERE aka Nokia) and TeleAtlas (now TomTom) Multinet are one of the most often used products for network analysis purposes (Esri uses them for building own routing data and services). The data is delivered in ESRI Shape format (file geodatabase available, too at least for Nokia) and need to be processed in order to be used with the Network Analyst extension. Navteq does provide Navstreets data in the compiled ESRI File Geodatabase from the Q1 2011 yet some data processing still will be required. Depending on how much information you want to include into your network dataset, you will need to perform some joins and geometry processing operations as well as use ArcGIS geoprocessing tools or scripting language, for instance, Python. The data coverage includes the whole world. Esri has developed a tool (Street Data Processing Tools) for processing the raw street data into a routable network dataset which can be used directly in ArcGIS Desktop with Network Analyst. I've been using those tools for a while and can recommend highly.
OpenStreetMap – a collaborative Web project that aims at creating a free digital world map. One can download all the data including, but not limited to, street network data, for instance, here. Street data do have much attributive information but one would need to perform a lot of manual data editing/processing to make it work with NA. The data coverage includes the whole world. There are some tools for automating this process here and here.
You can ask your local government agency if they have street data. Depending on what organization you represent, there is a chance you can get it for free (or it will cost you in case they sell it).