How can I predict traffic based on previous time series data? If I have a retail store and have a way to measure how many people enter my store every minute, and timestamp that data, how can I predict future foot traffic?  

I have looked into machine learning algorithms, but I'm not sure which one to use. In my test data, a year over year trend is more accurate compared to other things I've tried, like KNN (with what I think are sensible parameters and distance function).

It almost seems like this could be similar to financial modeling, where you deal with time series data. Any ideas?
The problem with models like KNN is that they do not take into account seasonality (time-dependent variations in trend).  To take those into account, you should use Time Series analysis.

For count data, such as yours, you can use generalized linear auto-regressive moving average models (GLARMA).  Fortunately, there is an R package that implements them (glarma).  

The vignette is a good resource for the theory behind the tool.