Adding wrapper elements in the_date() like in the_title()?

The Codex ( or Developer Resources ) is a fantastic tool when you’re unsure about a function. Looking at the parameter list for the_date() it says:

the_date( $format, $before, $after, $echo );

So you need to pass in a format as the first parameter, then your HTML tags like you have it. An example could look like this:

the_date( 'l, F j, Y', '<h4 class="entry-date">', '</h4>' );