Adding a Custom Menu Fields
You can do this with theme_menu_link().

A menu item's description is by default output as a tooltip (ie, in the title attribute).  Here's a thread that shows how to do take advantage of that using hook_menu_link() to achieve more or less the result you want.