ヘッダー内で相対/絶対位置を試すことができます。
CSS については、次のことを試してみてください。
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%;
}
ヘッダーに相対位置を設定することで、その各子要素を絶対位置に設定できます。これにより、各子要素をヘッダーの下部に配置できます。
重要な部分はCSSのpositionタグとleft、right、bottomタグです。http://jsfiddle.net/9patj/10/を参照してください