a common footwork mistake is not keeping it still! I see this all the time with people starting in bouldering, their footwork can be indecisive. You need to pick how and where you want to place your foot and do it. Don't keep moving it around, unless you plan to do this.
Use the correct parts of your foot/shoe. You want to only use the outside/indside edge(s), toe and occasionaly heel. These are the efficient areas of your shoes.

Try not to bang around. If your making a lot of noise then you are likely not moving efficiently. Pick how and where you want to move your foot and do it slowly, controlled and efficiently. Try not to throw your foot in the general direction and hope that it sticks.
Get correctly fitting shoes. Beginners often have shoes that are too big for them. Climbing shoes shouldn't have dead space. They should be tight on your foot. If they are not then your foot will be moving around inside the shoe.
Old shoes. again I see this a lot. Rental shoes can be pretty crappy. Consider buying a cheap pair instead. A very worn shoe will not stick to the wall as well as a newer one.
Trust it. This takes time. You have to learn that you can stand on a tiny hold and it will hold you. If your planning on using a foothold. Place it transfer your weight, believe that it won't move. If you get nervous you don't commit. You place less weight on the hold. You slip. You trust it less and the cycle gets worse. If you commit 100%, their is a greater chance your foot will stick.
This article covers some exercises to improve your footwork.