Driftwood and rocks are good choices. I have an awesome bit of driftwood which I have attached a plant to (this could be an idea to avoid your axolotl tearing it up) and it has a pretty cool hide - driftwood with hides can be hard to come across so be patient. I also found some nice flat rocks from a beach. I thoroughly boiled them and layed them out in the sun for a few days, tested if the rocks were safe, and then reboiled them again before adding to my tank. Be careful of some rocks, but slate is really good. Here's a pic for an idea.
I've also seen people using BPA Tupperware-sort of containers, cutting out a hole or two for the axolotl to fit through, sanding the edges down and then using aquarium silicon to glue down different rocks and such which looks pretty good too.
Check out the "post pictures of your tanks" thread for a load of inspiration!