Not getting into the method of how you capture all the data, because a MIDI controller sends out data in a continuous stream yes?http://en.wikipedia.org/wiki/MIDI
"MIDI messages are made up of 8-bit words (commonly called bytes) that are transmitted serially at 31.25 kbaud. "
What are you going to store all this recorded data onto?
Aruino's only have limited SRAM; you've got to move that data to a big memory chip, or if there will be a lot of it, to an SD card.
Checkout fat16lib's SDfat.h library for the latter.http://code.google.com/p/sdfatlib/
For the latter, you will have to decide how many seconds worth you want to store & size up memory accordingly.