Divs and spans are generic elements when no other element applies. Use them as a last resort. Inherently they have no padding or margin, most semantic elements have paddings and/or margins that are expected behavior.
If a <p> or <ul> or some other semantic element gives the text inside it meaning, use it, you can style it to act like a div if you need to. And that's really the point, use a container that says "here's the type of content I am holding." Divs and spans have no semantic meaning. A good example, often ignored: what is a navigation? A list of links.
Divs are block elements, who's original intent is to divide up a page layout. Think of them as boxes. "the perfect layout" IMO would have only divs for the main container block and boxes inside it. (Haven't seen one yet, but many come close. :-) )
Spans are inline elements, and just that, a span of text. If I want to emphasize a span of text, I'd first consider using <strong> or <em> and applying a style to it. But if I don't want to apply a semantic meaning to that span, I'll use span.
You can force **any** element to "act like" any other element with CSS, so there's really no reason to give a document div-itis simply because you're comfortable with divs. Use semantic elements wherever possible.
Side Note: Get the firebug plugin for firefox. After you figure out how to use it, you can select an element on the page, and it will show the CSS rules that are applied to the element, and which CSS file the CSS rule is applied from. It's VERY useful when working with someone else's design/styles.
To answer your question in the most simple way I can think of, div and span are just effectively 'boxes' that you can put content into (kind of like the cells in a table in terms of purpose).
These boxes can they be styled with CSS to get the required position on the page and style.
The difference between them is that a span is 'inline' and a div is a 'block'.
So you can have:
span span span span - on the same line
but not div div div div - it would be
div div div div
As the block level element always takes up a new line (without CSS styling to alter this behaviour)
Rocknbil is correct that it's better to use other elements where there is a semantic purpose to do so. This is being improved with html5 where there will be elements like <article>, <section>, <nav>, etc which will replace what would have been divs in current html.