The Julian Calendar
In 709 AUC (45 BCE), the real Julian calendar begins. Not only did Caesar decree the leap year rule, but he lengthened several months by putting 10 more days into the regular year. The new leap day was inserted exactly where the old leap month was, i.e., after the 24th of February. Both the 24th and the leap day were counted as vi Mar., the second was called bis vi or the bisextile.
In adding the new days to the calendar, Caesar tried to disturb the separation between festivals as little as possible (relative to the Kalends system of dating), and the new days were actually added just before the last day of each month that was extended, except for April, where it was inserted between the 6th and 5th Kalends. The month of July (Julius, from earlier Quinctilis) got its name in 44 BCE by decree of the senate. Notice that while our general rule for converting days of the month still applies, the Kalends numbering in the lengthened months is different in the Julian and Republican calendars. E.g., December 25 = vi kal Jan. in the Republican, but viii kal. Jan. in the Julian.
Because the pre-Julian Roman calendar was not regular, the custom of historians is to use the Julian calendar proleptically for earlier dates. That is, dates before 45 BCE, which are naturally recorded in different calendars, are translated into the Julian calendar. This convention explains one seeming paradox: the first year of the Julian calendar should have been a leap year in the new sense, but one was not celebrated that year. Thus the Kalends of January that year actually fell on January 2, 45 BCE.
After Caesar's death, his new rules were faithfully followed. Unfortunately, the new pontifices do not seem to have understood his rules quite as they were intended. Caesar specified a leap year at four-year intervals, and since Romans typically counted inclusively (see the remarks on Olympiads), they took this to mean every three years. So leap years were observed in 42 (712 AUC), 39, 36, 33, 30, 27, 24, 21, 18, 15, 12, and 9 BCE. At this point, someone must have brought the problem to Augustus Caesar's attention, because he decreed that there should be no leap year at all for the next 12 years, and carefully rephrased the rule to say "intercalate at five year intervals," so dense Romans would get their counting right. The first correctly observed leap year was in AD 8. Augustus also took the opportunity to rename the month Sextilis after himself at the same time, which is how we wound up with August, but there is no evidence to support the story that he lengthened that month so that it would not be inferior to Julius's month. In fact, as indicated above, the month lengths were all changed by Julius Caesar.