Recently I decided to do something about my handwriting, and I went from barely-legible scrawls to being able to write in any of a dozen fonts in the space of a few weeks (less than an hour practice a day). If you want to fix your handwriting, start by slowing down, and try to write just a few sentences in a nice, consistent style.

Think of it not as writing, but as doodling, just with letters being your doodles. Once you've played around like that for a few hours, look up some penmanship resources and try to mimic some writing styles. If you really get into it, try some calligraphy, it's a lot of fun. People regularly comment and compliment my handwriting now. (But if I go back to top-speed, it becomes a scrawl again.)