The only difference between the two elements is semantics. Both elements, by default, have the CSS rule display: block (hence block-level) applied to them; nothing more (except somewhat extra margin in some instances). However, as aforementioned, they both different greatly in terms of semantics.
The <p> element, as its name somewhat implies, is for paragraphs. Thus, <p> should be used when you want to create blocks of paragraph text.
The <div> element, however, has little to no meaning semantically and therefore can be used as a generic block-level element — most commonly, people use it within layouts because it is meaningless semantically and can be used for generally anything you might require a block-level element for.
If you don't quite get what I'm referring to when I say "semantic markup", you might consider checking this post.
wow. thank you fred from PLANET CODE. Your knowledge is truly impressive. You've opened my eyes to whole new vistas with each post you answer.
I'm definitely hip to the notion that STRUCTURE=GOOD when you're talking about web content and layout. I used to work for a desktop production company automating DTP tasks and quickly realized that STRUCTURE made life much easier when you're dealing with information in any bulk capacity. All the browsers, spiders, search engines, and indexes need this info so that we (and our descendants) will be able to catalog and make sense of all our musings long after we are gone. The whole advantage that electronic information provides over printed material is STRUCTURE STRUCTURE STRUCTURE. you can't click a SEARCH button on a book and find what you're after.