What are the differences between Normal and Utiltiy Categories
From a regulatory standpoint the governing regulation is FAR 23 (airworthiness standards for what we'd generally call "small" airplanes - Normal, Utility, Acrobatic, and Commuter category). 

FAR 23.3 is probably what you're interested in, and tells us:


Normal Category is limited to airplanes that have a seating configuration, excluding pilot seats, of nine or less, a maximum certificated takeoff weight of 12,500 pounds or less, and intended for nonacrobatic operation.
They go on to specify that nonacrobatic operation includes:


Any maneuver incident to normal flying
(for very vanilla definitions of "normal" - they expect you to use some common sense here!)
Stalls (except "whip stalls")
What most pilots recognize as the "commercial flight test maneuvers": Lazy eights, chandelles, and steep turns, but with an angle of bank not greater than 60 degrees in any of these maneuvers.

Utility Category is the same type and size of airplane, but approved for "limited acrobatic operations" - this may include intentional spins, as well as the "commercial maneuvers" with higher bank angles (greater than 60 degrees, up to 90 degrees).
Acrobatic Category is the same type and size of airplane, but approved for acrobatics  without any restrictions "other than those shown to be necessary as a result of required flight tests" -- basically "airplanes that can go upside-down".


The commuter category is boring: It's basically the normal category, but with more engines (at least 2) and more seats (up to a maximum of 19). Commuter category aircraft can also have a higher maximum takeoff weight (up to 19,000 pounds).

An aircraft can be certificated in any combination of the Normal, Utility, and Acrobatic categories if the aircraft meets the requirements of the appropriate category (as specified later in FAR 23).  An aircraft certificated in the Commuter category may not be certificated in any of the other categories however.



Generally the restrictions you find on aircraft are not regulatory ones (from the FARs) but Operating Limitations (in the POH or placarded on the aircraft) which you must comply with (per Part 91 of the FARs).  

For example, the Cessna 172 and the Piper Warrior are both dual-category aircraft (Normal and Utility), and specify a "Utility Category CG Envelope" in their weight and balance charts.

The Piper Warrior is not approved for spins in the utility category (they are placarded with SPINS PROHIBITED). they also have other restrictions for utility category operations which are found in the POH and on aircraft placards (e.g. UTILITY CATEGORY - NO BAGGAGE OR AFT PASSENGERS, and maximum entry speeds for other acrobatic maneuvers).

Most Cessna 172s are approved for spins in the utility category and are not placarded against them. (Certain aircraft with specific STOL kits installed are disapproved as a result of the kit, and have placards prohibiting them).