I currently have 3 divs within a HTML5 header tag lined up (to the left - a search box, the center - a logo area and a div to the right - for social media icons).

That seems to be fine, however, I'm having difficulty positioning the left and right elements within those divs to the bottom AND having both the left and right divs to be affected by the size of the logo area. For example, if my logo was x height, it would push the left and right divs further down as the logo's size height increased.

I've written up a quick example to illustrate hopefully what I'm talking about.. http://jsfiddle.net/9patj/

If anyone could help, that would be great and perhaps a bonus in walking me through how it is achieved would be really appreciated.

You could try relative/absolute positioning within the header.

For the CSS, you might try:

header {
    margin: 0px 29px 29px 29px;
    background: #CCC;
    width:960px;
    height: 160px;
    vertical-align: bottom;
    display: table-cell;
    position: relative;
}

#search {
    float:left;
    width:215px;
    background-color:red;
    position: absolute;
    bottom: 0px;
    left: 0px;
}

#social {
    float:right;
    width:215px;
    background-color:yellow;
    position: absolute;
    bottom: 0px;
    right: 0px;
}

#logo {
    float:center;
    text-align:center;
    position: absolute;
    bottom: 0px;
    left: 50%;
}

By setting relative positioning on the header, you can set each of its child elements to absolute positioning. This will allow you to place each child element at the bottom of the header.

Important parts are the position CSS tag and left, right and bottom tags. See http://jsfiddle.net/9patj/10/