Definition
"Dedicated server" refers to a program which only functions as a server to which clients can connect. "Shared servers" are processes which handle both the server and the client side of a game. Garry's Mod functions as a shared server with no additional setup, while hosting a dedicated server means either renting one or using a different program, called "srcds."
Stability
Dedicated servers are by far the more stable of the two types. While shared servers close as soon as the game closes or crashes, dedicated servers and the computers on which they run are designed to run for weeks or months at a time without interruption. Moreover, dedicated servers will often have backup functions, meaning that the players' work on the server will be uninterrupted between sessions.
Speed
Shared servers run using whatever Internet provider the client runs, while dedicated servers are often set up in computing centers with much more powerful network connections. While most home Internet setups have no problems with one game connection, a shared server multiplies that one connection by the number of players connected. This can quickly overwhelm the network and slow or interrupt game play.
Availibility
Shared servers are vastly more available to someone looking to set up a place to play than dedicated servers. This is because every copy of Garry's Mod comes with built-in server capability. However, dedicated servers are not out of reach for the average user, and generally run less than an MMO subscription per month.