Practice makes perfect.
My own handwriting (on paper) went from hideous to beautiful enough to get me compliments. I accomplished this by making a conscious effort to write neatly when taking lecture notes (even if it meant writing slowly), as well as writing things over and over until it was satisfactory (often compared to a sample).
I don't feel like it really slowed me down all that much. Occasionally, during exams or fast speeches, I still revert to uglier handwriting in hopes of saving precious seconds, but rarely gain all that much. Conversely, I doubt you will really end up losing significant lecture time by writing neatly during real lectures, but of course you can always try it out in a mock lecture (note that writing neatly the at first will be much slower because you are not used to it). However, it did take me time to get better: The bulk of the improvement was over several months, and even after several years the quality of my handwriting was changing, though not as noticeably. Keep in mind that I would spend several hours taking notes in lectures every day, in addition to writing in my free time. Perhaps you can be a more diligent student than I was, but I would still say don't expect big changes overnight.
That said, I don't see why my experience wouldn't translate to board writing also. If you want your handwriting to be better, find a board and keep writing on it until it is better. It helps to actively force yourself to write neater.
As I said, lectures are a great opportunity for getting some regular, intense practice. If you can at all afford to slow down even a little bit, you should do so and you can get results sooner.
Regardless of whether you decide to risk slowing down your lectures, you can always practice by yourself. As a grad student you will almost certainly have access to a blackboard. Go up there and write on it until your hand gets tired. Then erase and do it again. Keep an eye out for motions that make letters come out particularly ugly or pretty.
Small children learn to write by tracing dashed lines of letter shapes. You could simulate this by using some kind of projector to project "worksheets" on the board (with a blackboard, white on black would probably look better, and a dim room helps).
If you feel like this is too much of a waste of time, write out material that you are having difficulty learning, research ideas and notes of future lectures. That way you are both practicing your handwriting AND doing some useful work.