Georeferencing is the process of assigning a coordinate system to a scanned image (map, aerial photo) in GIS. A georeferenced image does not have all scale (vertical scale) distortion removed, so if you georeference an air photo with a large amount of vertical relief across the scene, the scale of the image and the accuracy of the alignment will vary across the scene. For scanned maps, the fit should be better, as nearly all maps are planimetric (designed with scale distortions removed).
To georeference a hardcopy map or photo, you will need both a high-quality scan of the original, plus a reference layer. The reference layer can be in any coordinate system, but you should have five points that you can see on both the scanned image and the reference layer. These should be features that are unlikely to move over time, such as road intersections, bedrock outcrops, or street corners.
Once georeferencing has been applied to your scan, you may use it in conjunction with other layers either as a backdrop for a map or as a source from which you can create new features. The quality of the original map or photo, the resolution of the scan, and your ability to locate high-quality control points will all affect how well the georeferenced image will fit with other features in your GIS.
Here is a document that describes the georeferencing process in ArcGIS. The instructions should work for both ArcGIS 9.x and 10.x.