You would want a flexible adhesive, as the rubber soles will have some movement throughout its thickness.
A good quality contact cement will bond well with both the rubber and with the wood, as long as you have a clean smooth surface on the wood. The rubber should also be cleaned with a solvent such as denatured alcohol or acetone, to ensure there is no oil or grease.
Unfortunately, a good quality contact cement will make it difficult to later replace the rubber.
That leaves a rather obvious option known as rubber adhesive. This is not to be confused with rubber cement, often used in offices and print shops to bond paper layers. The appearance of both products are similar, but the rubber adhesive products will be thicker.
Some of the adhesives work in a manner similar to contact cement, in that the layers are applied to both surfaces and allowed to become tacky, sometimes even requiring that the adhesive become dry. When placed into contact, the bond is quite strong.
When removal becomes necessary, it is likely that you will have to sand away the residual adhesive from the wood, or use a solvent that will not damage the finish of the wood. Goo Gone or similar citrus based removal agents may prove useful.