The "Footer" is shown at the bottom of all your pages. Generally the links are the same as what you have in your menus.
Header
There is also an option to simply upload a logo file when in the Header & Footer tab.
If using a logo file, the size of your logo file depends on your theme and the space in the header. Generally you don't want the logo file too large. 80 pixels in height is a good place to start. After you have added a logo to your header, go to Design -> Edit My Theme and make adjustments to the header section if needed.
Mobile Header
The mobile header option allows you to have a different (smaller) logo / header when showing on mobile devices or devices with a screen resolution less than 800 pixels wide. It is best to upload a small logo here or just enter in text so it doesn't make the pages "squished" if you main logo is too large.
The suggest max width for the mobile logo or header is 250-280px, but you may want to experiment on size.