Filter Search Results using a custom field

Hi,

We want to allow users to filter search results by what we believe will be a custom field.

What we have currently:

Places
– Categories
– Locations

When someone sees a list of either all places, places in a category or places in a location – we then want to be able to filter by another value (type).

Ideally, we would add this type to the main search bar so we would have

Places – Categories – Locations – Type

From our reading it looks like we could do this with a custom field – the field would have the values (as an example) of A, B, C & D.

Questions:
– how do we add a custom field to places?
– how do we then add this to the menu?

Many Thanks,
Andrew