Combining regression with time series

Using an existing time series of supermarket sales data I need to make a forecast. Basically a simple exponential smoothing model explains future values fairly well. But besides being dependent on the past values there is also a strong dependency on an external variable, the amount of spend on newspaper advertising, and I would like to include that in the model.

Ideally I would like to use a least-squares regression with two regressors, one for the time series component (exponential smoothing, AR, MA, or any other suitable method) and one for ad spending.

So far I have two ideas but both have flaws:

1) An AR(1) process plus the ad spending variable would be easy to model with least squares but AR(1) uses only the previous day's information and I already know that more past terms should be included, such as in exponential smoothing.

2) I could first apply exponential smoothing to get a smoothed time series and then do a least squares regression on the ad spending with it. But then the two effects would be calculated separately and I am afraid of killing some of the ad spending effects if I smooth the time series before it.

Any ideas for a simple model with a predictor for the time series component and one for the ad spending?
I don't know how it works yet, I will figure it out myself (for a real world situation) in a couple of weeks but; you know how to estimate an Arima model i guess. You can add extra independent variables by using so called ARMAX models, (X standing for the independent added variables). I guess, if you know how to estimate and interpret Arima models you could also do the same for ARMAX model. Spss has a function where you can add these extra variables.