I've noticed that my cats pat the area where they intend to lay down for a pretty long time, 30 seconds to up to 3 minutes. Interestingly enough, this is only on soft surfaces, never on hard surfaces such as the floor. Why do they do this?
Your cat is kneading. In kittens, cats knead their mothers to get more milk out of them. An adult cat will knead when it's feeling content because it associates the motion with the comforts of nursing and its mom. Some cats even suckle on what they're kneading, though I've never seen my cat do it. Beware, though, as my cat sneaks into my bed at night and painfully kneads my face. It's less funny than it sounds.
This is an instinct every cat has. They only do this on soft surfaces and they do this to be sure the place can carry their weight. Out in nature, a very soft area is an unsafe area and it is not only cats that react to this. Humans do it too! If you are out walking and suddenly step into a very soft ground you stop without thinking.
If your cat is on a hard surface it doesn't pat the area before laying down, it only walks in a circle or two and lays down.