In the past I've used the Day and Name or Month and Name settings.
Should the date structure be omitted and just have /%postname%/ ?
Ie does having the date information reduce the quality of the url?
The best permalink structure for seo is /%category%/%postname%/
This permalink structure gives you the most keywords loaded into the URL of your post. Since the category that you’ve placed your post under usually relates to the post title, you will have an extra SEO benefit if other websites use that permalink structure to link your post.
After reading over the link Mike shared below I felt I should also mention that starting the permalink string with %postname%, %category%, %tag%, or %author% will invoke WordPress's "use_verbose_page_rules" which will cause the rewrite matching system to generate individual rules for every Page, then check those first. If you have lots of pages, this is a big hit to the system. The performance hit happens at about the 50+ page mark.
In order to have the ability to scale your site on a larger level you should start the permalink structure with a number like: /%year%/%category%/%postname%/
Your pages will always use the /%pagename%/ permalink structure any time you enable permalinks so the /%year%/%category%/%postname%/ will only be applied to your posts.
If your site is more CMS than blog the optimal SEO url structure would be to use child pages where the parent page could be considered a category.
For example a university website might have a parent page "Campus Offices" with child pages of "Business Affairs", "Athletics" etc.. Then URLS would like this: www.university.edu/campus-offices/athletics/ which is great for the user experience and seo.
Put the terms you need SEO wise in the slug. The permalink structure is pretty unimportant then. Better invest your time and money into content instead of finding the holy grail in permalink optimization. Unless you don't do all the time and adopt accordingly and integrate it into a whole SEO strategy, you won't get anything specific out of it.
But one criteria SEO wise is the speed your site will react now these days. So to say your permalinks should have good performance, so adding the ID is very helpful to give WP some speed. There's nothing wrong in having the ID part of the permalink these days, I wonder why this is not suggested more often (in the end it doesn't help with wordpress permalinks? :).
re: Does having the date information reduce the quality of the url?
Obviously, definitions of quality vary. I think month and day are unhelpful.
If you like dating your posts then /%year%/%postname%/ is the cleanest, as long as you ensure your slug contains relevant keywords.
People do sometimes add the current year to a search query, and it can help when people are picking between different URLs (if competing URLs look like they could contain outdated information). Couple this to the performance tips also on this page and it seems that the year is a good thing to start with.
The dangers of category is that categories change. The year you posted a post changes considerably less often.