Given how cheap storage is now, I wouldn't be surprised if they just had a few thousand >4GB SD or microSD cards, each labelled with a number, and randomly chose which one to carry each time - or if they carried a bunch of them around in a briefcase. Assuming that they're using one time pads, that is.
Unless things have changed significantly since I was in the Navy (doubtful), they still use things like this to store crypto keys: http://en.wikipedia.org/wiki/AN/CYZ-10
