zink0xide,
As others have mentioned, you can use practically any 8-bit serial-to-parallel 'sinking' driver IC or "constant current" sinking driver IC connected to the segments and five PNP or P-channel MOSFET 'sourcing' column drivers. The 74HC595 is a little "light duty" for this application but seems to hold up well. A better choice might be the TPIC6C595.
Here's an example of my MacMux? design for that Sparkfun display. I apologize for not yet having enough experience to back up the design with an Arduino software driver example but I could provide a C example for PIC if someone wants to take a stab at coding my method for Arduino.
The MacMux? design uses the PWM module with a period equal to the digit scan interval (1 to 2 msecs) to multiplex the column driver lines. When the PWM signal goes high (display "off") at the beginning of each digit scan interval the column driver lines are re-tasked for use as and lines to load the 74HC595 shift register. The column driver lines are then reset to the correct column select pattern (only one line low) before the PWM line goes back low (display "on"). Complete fade-to-black brightness control is a matter of setting the PWM duty cycle to some value between approximately 5% and 100% in the main program. PWM duty cycle is inversely proportional to display brightness with a 5% duty cycle = full brightness and a 100% duty cycle = black.
Regards, Mike