Forecasting is a big field, so it will be hard to give a simple answer. I'd recommend starting with a very simple model. Simple models are often surprisingly hard to beat in terms of forecasting accuracy.

Look first at exponential smoothing with a seasonality of 7, to capture day of week effects, which will quite probably be the main driver of store visits. That will give you a useful baseline, and only once you have mastered that, you should try improving on that. (And I forecast that you won't find that easy.)

Holidays should probably be the next thing to look at. Here, you may want to switch from exponential smoothing to ARIMAX models, with additional explanatory variables around the holidays. Not as simple and easily understood as smoothing, but it can more easily capture external info (although state space formulations of smoothing can do so, too).

At this point, you will want to think about what kind of store you are looking at. Grocery is easy, very stable. Fashion is more volatile, with multiple seasons per year and traffic patterns following these seasons (and markdown periods). DIY may depend on the weather, as with everyone rushing to buy snowplowers when the first snow falls. And so on.

Leave weather for last. Yes, weather will have an impact. But you will need to include weather forecasts in your models, not actuals, since you don't yet know the actual weather for tomorrow! This of course adds a level of uncertainty. Don't use the actual weather in your forecasts for assessing your model, since you will lose this additional uncertainty, and your models will necessarily look too good - you will be too sure of yourself. And if you want to use your forecasts in a production environment, you will of course need to worry about the data feed, and what happens if the feed is broken and no weather forecast is available... While weather data may improve your forecasts, you will have to think about whether the additional hassle is worth the accuracy improvement.

You write that your current forecasts are "highly inaccurate". Forecasting is an inexact science, and no forecast will ever be perfect. Be careful about your expectations and about accuracy targets. Don't trust published forecasting accuracy benchmarks.

I highly recommend this free, open source textbook on forecasting. You will find much about exponential smoothing, ARIMA, error measures and so forth in there.

Forecasting is a big field, so it will be hard to give a simple answer. I'd recommend starting with a very simple model. Simple models are often surprisingly hard to beat in terms of forecasting accuracy.

Look first at exponential smoothing with a seasonality of 7, to capture day of week effects, which will quite probably be the main driver of store visits. That will give you a useful baseline, and only once you have mastered that, you should try improving on that. (And I forecast that you won't find that easy.)

Holidays should probably be the next thing to look at. Here, you may want to switch from exponential smoothing to ARIMAX models, with additional explanatory variables around the holidays. Not as simple and easily understood as smoothing, but it can more easily capture external info (although state space formulations of smoothing can do so, too).

At this point, you will want to think about what kind of store you are looking at. Grocery is easy, very stable. Fashion is more volatile, with multiple seasons per year and traffic patterns following these seasons (and markdown periods). Do-it-yourself and home improvement store traffic may depend on the weather, as with everyone rushing to buy snowplowers when the first snow falls. And so on.

Leave weather for last. Yes, weather will have an impact. But you will need to include weather forecasts in your models, not actuals, since you don't yet know the actual weather for tomorrow! This of course adds a level of uncertainty. Don't use the actual weather in your forecasts for assessing your model, since you will lose this additional uncertainty, and your models will necessarily look too good - you will be too sure of yourself. And if you want to use your forecasts in a production environment, you will of course need to worry about the data feed, and what happens if the feed is broken and no weather forecast is available... While weather data may improve your forecasts, you will have to think about whether the additional hassle is worth the accuracy improvement.

You write that your current forecasts are "highly inaccurate". Forecasting is an inexact science, and no forecast will ever be perfect. Be careful about your expectations and about accuracy targets. Don't trust published forecasting accuracy benchmarks.

I highly recommend this free, open source textbook on forecasting. You will find much about exponential smoothing, ARIMA, error measures and so forth in there.