I've always kept a checkbook (well, now it's on the computer) register, but I just recently started a formal budget. I'm using these free applications:
Pear Budget (a fancy Excel spreadsheet) for the budget and
Cashbox for my register.
I'm really happy with these so far. I started off with my own spreadsheet but found Pear Budget more elegant and more advanced than anything I could take the time to do.