As the sample that Twitter provides consists of 1% of all tweets. I expected it to give me random tweets from the past and present - but when I wrote a piece of code in Processing using Twitter4j, it just retrieves the real-time tweets.
That's incorrect, the public streams "offer samples of the public data flowing through Twitter", so that is real-time data and not historical.
If you did want to retrieve historical Tweets with Twitter4J, you could use the Twitter#search(Query query) method to do it.