Widget are small self-contained blocks of code that execute a single well defined action. They can be as simple as displaying the pages Author, as as complex as displaying a feature set of ads. The key point though is that they must, from a HTML perspective be self contained, stand alone.
Widgets are added to sidebars. Sidebars, as the name suggests, are generally the side areas, either side (no punn intended) of the main content area. However, there is nothing stopping you registering the header or footer as a ‘Sidebar’ area.
Widgets can be delivered either in Themes or Plugins or, of course you can add them directly to your own site. Generally , apart from home grown Widgetsw, using the Plugin as a deliery mechansim is considered preferable, because the functionality is then available across all themes.