Need help with PHP coding

Hello all. I’ve just recently taken my blog and set it up on my personal web site. I have almost everything how I would like it to be, matching the rest of the site layout, etc. The only thing I just cannot do is get the previous/next page links to show up how I would like. Here is a link to my blog so you can first see what I am talking about:

http://robertlbryant.com/blog/

Where it has the box that says “Older Entries || ” is where I am having problems. I noticed how in the permalink pages, it will show the name of the previous and next entries, if there are any. I would like to somehow get that box to always have the name of the previous and next entries, regardless of being on a permalink page or not (if this is possible). It would also be nice if there were a way that I could make something that says “Latest Entry” or “Earliest Entry” if there are no links to show. Now, where I am wanting this to be is in the header, as I have it setup so far. Here is some pseudo-code for what I’d like:

if permalink_page
*name of post prior* || *name of post next*
if no_prior_post
“Earliest Post”
if no_next_post
“Latest Post”
else
Older Entries || Newer Entries
if no_older_entries
“Earliest Post”
if no_newer_entries
“Latest Post”

It’d be nice if I can just use the names of the posts in both permalink and non-permalink pages, the else wouldn’t be necessary. I hope I’m making this clear enough for what I would like. Thanks for any help.