One basic function that the Edge units share is the ability to record your route and other ride data. When you get home you can upload it to your computer and see the route on a map and see your speed, elevation, etc. at points along the route.
The Edge 500 can show a route on the screen and your position along it. You lay the route out on your computer and download to the device. It has no map or database so won't show roads or landmarks and does not tell you when to turn. For example, if you see the route take a sharp right on screen, turn right. If you don't, you'll see that you're off the route and need to find your way back on to it.
The 800 has maps so will show roads and landmarks. Like auto GPSs you can put in a address or search for something in it's database and it will navigate you to it with turn by turn instructions. It chooses the route in this case, which is often not the route you would choose, so what most do is lay the route out on their computer and download to the device. The 800 will show this route on the map and provide turn by turn instructions giving you warning ahead of time that a turn is coming up and showing a diagram of the upcoming turn, similar to auto GPSs.
There are other training functions and features as well.