Product attributes are used in Magento to help customers drill down via Layered Navigation.  More detailed and appropriate product attributes greatly improves the visibility of products relevant to a customer's requirements.

To add a new attribute, select Catalog > Attributes > Manage Attributes and you'll be presented with the following screen:

While there's a lot going on here, most of the fields can be left as default.  The more important fields are:

  1. Attribute Code: assign a unique Attribute Code for this attribute.  This is a unique machine-friendly identifier with no spaces, such as 'material_colour' or 'size'
  2. Input Type: select an input type.  'Drop-down', 'Text' and 'Multiply select' are frequently used attributes.  If you want to include this attribute in layered navigation, it must be of types 'Dropdown', 'Multiple select' or 'Price'
  3. Values Required: Selecting 'Yes' here will ensure products cannot be added without this field being filled in.
  4. Use in Quick Search: if selected, this attribute will be searchable via front-end searches.  Generally you want this to be 'Yes'.
  5. Use in Advanced Search: if selected, this attribute will appear as a unique field in the front-end 'advanced search', which may or may not be necessary.
  6. Use in Layered Navigation: whether to show this attribute as selectable for filtering products via the front-end Layered Navigation system.  This is one of the most powerful aspects of product attributes and an extremely useful way to discover products.
  7. Use in Promo Rules: whether to enable promotional or shopping cart rules based on this attribute. This can be useful in applying specific discount rules: imagine a St Patrick's Day promotion where everything in store which is green gets 10% off...
  8. Position: a number which indicates the position in Layered Navigation. Higher numbers appear lower in the list.
  9. Visible on Product View Page on Front-end: whether to display this attribute on the product page, depending on theme, this is frequently in a tab such as 'details'

Once you're satisfied with this page, it's now time to set the attribute name and options as they are visible in the front end.  The attribute code set earlier is used as a unique identifier and isn't displayed to customers.  From the sidebar on the left, select 'Manage Label / Options' and you will be presented with a screen thus:

Here you can see an example attribute 'Colour', which is a 'dropdown' attribute with a few options added.  The primary fields to fill in are the 'Admin' fields, which is what this attribute value will look like in the backend, and what it defaults to in the front end if you don't specify a different value in 'Default Store View'.  

'Default Store View', 'Position' and 'Is Default' are all optional fields and can be safely ignored in most cases.

See the Magento official documentation for more details: