When using wp_nav_menu you can pass arguments to it which help you style the output, look at:
$container
Whether to wrap the ul, and what to wrap it with. Allowed tags are div and nav. Use false for no container e.g. container => false .
$container_class
the class that is applied to the container.
$container_id
The ID that is applied to the container.
$menu_class
CSS class to use for the containing div element which forms the default menu, or the ul element when a custom menu is configured in the admin interface.
$before
Output text before the of the link.
$after
Output text after the of the link.
$link_before
Output text before the link text.
$link_after
Output text after the link text.
$items_wrap
Whatever to wrap the items with an ul, and how to wrap them with.
So in you case you can use
array( 'link_before' => '<div class="your_class">' , 'link_after' => '</div>');
But if you ask me you can probably do what you want with the classes WordPress prints out anyway.
http://codex.wordpress.org/Function_Reference/wp_get_nav_menu_items