Collect statistics essentially generates the demographics information of the actual table rows.The statistics are divided into 100 intervals (100 intervals till V2r6 and upto 200 intervals from version 12).Each interval in the statistics covers information like the number of values in the interval, number of unique values,frequently occuring values,number of nulls etc., the parsing engine makes use of this information to estimate the number of rows that can be returned to spool in each step of the query that user has submitted.
You can find more information about statistics in Teradata Manuals.
To add a few cents to Leo's dollars, also ensure that if you collected stats on any table, do keep collecting as the data in the table changes.
If you can't collect it on a regular basis, make sure you don't collect it on highly volatile columns (which may also mean column combinations).
Volatility could be from the perspective of the entire table (like say the telephone numbers changed due to an NPA-Nxx split) or just from the perspective of an individual query (say a query that retrieves information specific only to a biller after it's loaded to a line table to generate a summary data).
Also if a column contains high amount of nulls, it may not be a good candidate for multicolumn stats (this issue I believe is fixed in 12.0), collecting individual stats on it would be a better idea under those circumstances.