As you noted, the biggest thing is practice. But here are a few specific tips that I believe significantly improved my programming ability:
1) Try to get the implementation 100% correct on the first try. I don't mean that you should implement the whole system in one go, but the part you implement should do exactly what you want it to do (i.e. no typos, mixed up variable names, etc.). At first I thought this was a bit harsh, but it was amazing how much debugging you can avoid with a little more focus in the beginning. Also, it forces you to adopt good coding practices and make sure your algorithms are fully specified.
2) Don't tolerate tedious work. If there's any part of your workflow that's tedious, spend a lot of effort trying to minimize it. Some examples of things you might do: write a script, refactor your code, use a better editor, use a different programming language. You won't learn much from changing 100 variable names to camel-case, other than how painful it is. You will learn something from writing a tool to help you do that.
3) Think about how various libraries and frameworks you use are implemented, especially if they have features that seem like "magic". Try to reverse-engineer their design, or take a look at their source code (if available). This is a natural way to gain exposure to new ideas.
Regarding more "theoretical" subjects like algorithms and data structures that you might need to know for interviews, you could practice on programming contest websites (e.g. www.codeforces.com) or read some textbooks. However, in my opinion, those are not nearly as important for a software developer as the three things mentioned above.