Edward Caissie

This page may help answer some more of your questions: http://codex.wordpress.org/Template_Hierarchy

It will describe how the template files of a theme work together to display the content of your blog.

Off the cuff …

You will have to edit the function sandbox_globalnav() in the functions.php template file.

function sandbox_globalnav() {
	if ( $menu = str_replace( array( "\r", "\n", "\t" ), '', wp_list_pages('title_li=&sort_column=menu_order&echo=0') ) )
		$menu = '<ul>' . $menu . '</ul>';
	$menu = '<div id="menu">' . $menu . "</div>\n";
	echo apply_filters( 'globalnav_menu', $menu ); // Filter to override default globalnav: globalnav_menu
}

Change the line: $menu = '<ul>' . $menu . '</ul>'; to:

$menu = '<ul>' . $menu . '<li><a href="http://link-to-your-gallery">Gallery Link</a></li>' . '</ul>';

… untested, but it should work (or at least get you started) …

A link to your blog and the current active theme you are trying to edit would be very useful in making suggestions for you to use.

The time is being displayed with this code (snippet, around line 11):

<small>Posted in <?php the_category(', ') ?> on <?php the_time('F jS, Y') ?>

This is found in your index.php file, and most likely several other template files. If you remove the part: on <?php the_time('F jS, Y') ?> the time should no longer be displayed.

I believe you are wanting to make a category template, see this page in the codex for more details: http://codex.wordpress.org/Category_Templates

Although there are numerous recent post plugins available I believe the question is will your theme support the placement you are looking for?

I would think you could edit your comments.php template file in your active theme. Just search for the text and replace it with your preferred wording.

You can also use the HTML tag <del>

http://w3schools.com/tags/tag_del.asp

Which appears to replace the deprecated ‘s’ and ‘strike’ tags per the link @jdingman provided