Data Setup for Differences-in-Differences Which setup is correct for a difference in difference regression model using 
$Y_{ist} = \alpha +\gamma_s*T + \lambda d_t + \delta*(T*d_t)+ \epsilon_{ist}$
where T is a dummy which is equal to 1 if the observation is from the treatment group
    and d is a dummy which is equal to 1 in the time period after the treatment occurred
1) Random samples from each group and time (i.e. 4 random samples) 
or
2) Panel data where the same units are tracked over both time periods?
Does it matter and if not, can OLS be used with either case?
 A: A key assumption of difference-in-differences (DID) is that both groups have a common trend in the outcome variable before the treatment. This is important in order to make the argument that the change for the treated group is because of the treatment and not because the two groups were already different from each other to begin with.
If you sample different people before and after the treatment this will weaken the argument unless your samples from the treatment and control groups are actually random and large. So it well might happen that somebody is going to ask you: "How can you make sure that the effect is due to the treatment and not just because you sampled different people?" - and that will be difficult to answer. This question you can avoid by using panel data because there you track the same statistical units over time and generally this is the more solid approach.
To answer your last question: yes the data matters but you can surely use OLS to estimate your equation above. An important thing which in the past was often overlooked is the correct estimation of the standard errors. If you don't correct them, serial correlation will underestimate them by a good amount and you will find significant effects even though you probably shouldn't. As a reference and suggestions for how to deal with this problem see Bertrand et al. (2004) "How Much Should We Trust Differences-In-Differences Estimates?".
As a last thing, if you have aggregate data (e.g. at the state level) or if you can easily aggregate yours and if you want to use a more recent econometric method than DID, you might want to have a look at Abadie et al. (2010) "Synthetic Control Methods for Comparative Case Studies". The synthetic control method is increasingly used in nowadays research and there exist well documented routines for R and Stata. Maybe this is something interesting for you as well.
