Drupal provides a clean way of formatting dates any way you want throughout the entire site.

Earlier today, Rachel commented that an upcoming events block on a site we are working on displayed the date in an ugly format. So I changed it and for anyone who is interested, here is the step-by-step process for doing so.
Navigate to admin/settings/date-time/formats/add. Click on the 'Add format' sub-tab. Enter a date format string conforming to PHP date function standards.

For this project I chose "D, M jS \a\t g:i a" That format string looks intimidating, but it's straight forward. Each character in the format string will be replaced by a date component as defined in this table.
So we get:
D, M jS \a\t g:i a
Tue, May 19th at 2:56 pm
Navigate to settings/date-time/formats. From this page you will need to create a new format name and select the format you just defined. Here I chose the name "Event Block."

You can map your new format to an existing named format (Long, Medium, Short) or add your own.

In our case, we just wanted this format to display on the event block. Since the block is a view, we modify the date field for the view.

You can edit the display of date cck fields by navigating to admin/content/node-type/[My Content Type]/display/basic and selecting the format to display for nodes and teasers.
You can modify the "submitted by" part of the node two ways.
The "submitted by" part of nodes is generated by a theme function called theme_node_submitted. This theme function assumes the "medium" date format. So either set "medium" display to your custom format or override theme_node_submitted in your template.php file.
function mycustomtheme_node_submitted($node) { return t('Submitted by !username on @datetime', array( '!username' => theme('username', $node), '@datetime' => format_date($node->created, 'myformatname'), )); }

Much more readable. That was easy.