A boring answer to this question is that it was simple incremental changes driven by random mutations and natural selection (eg. evolution). For example, we might have started to occasional plant the seeds of plants as we found them, which could become us regularly doing so. Then we might have started moving the seeds to more central locations, and eventually arrive at agriculture as we know it today. These adaptations may have started before homo-sapiens. If it happened long enough before (so that there is another species with a common ancestor that did this), we could check this by looking for agricultural tendencies in species related to us (If anyone is aware of research on this hypothesis, please post).
A more interesting hypothesis is that agriculture was the result of an abiotic change. Instead of gradually developing agricultural tendencies, we 'immediately' became agricultural following some other event, such as a change in climate. This seems to be consistent with my understanding of climate history, which puts us in a relatively short window of nice climate.