The dilema of what to do with your navigation on the small devices is one of the toughest when it comes to responsive design.
Navigation is second to content when it comes to importance on your site, check out these emerging patterns to make sure your hierarchy is useful across the range of media queries.
With responsive design only being applied to large sites during 2012 we are still on the way towards best practice for navigation. There are three main ideas behind the navigation approach though: 1) Off Canvas; 2) Link to bottom; 3) display:none;display:block;