How to put two tables in a table* element so that the tables appear side by side in a two column layout scientific paper?

You should use the subfig package.

\begin{table*}
\subfloat[First caption]{\begin{tabular}{...}...\end{tabular}}
\subfloat[Second caption]{\begin{tabular}{...}...\end{tabular}}
\caption{Overall caption}
\end{table*}

This can be used in conjunction with the floatrow package. See the subfig documentation for an example that aligns captions using floatrow.

EDIT:
Your example has an extra \begin{table} that doesn't belong. It also has a blank line which causes TeX to start a new paragraph which is why one table appears on top of the other.

Here's a complete example where I've also cleaned up your tables following the guidelines given in the documentation to the booktabs package.

\documentclass[twocolumn]{article}
\usepackage{subfig}
\usepackage{booktabs}
\begin{document}
\begin{table*}
\subfloat[Before processing]{
\begin{tabular}{ccccc}
\toprule
Year & Month & Country & State & Impressions\\
\midrule
2007 & JAN & IN & TN & 3\\
2007 & JAN & IN & TN & 1\\
\bottomrule 
\end{tabular}
}%
\hfill
\subfloat[After processing]{
\begin{tabular}{ccccc}
\toprule 
Year & Month & Country & State & Impressions\\
\midrule 
2007 & JAN & IN & TN & 7\\
2007 & FEB & IN & KA & 13\\
\bottomrule 
\end{tabular}
}
\caption{overall}
\end{table*}
\end{document}

Complying with the request of TH., here comes an example that uses the »subcaption« package (shipped with caption). The tables will appear on top of page 3 of the resulting document.

\documentclass[11pt,a4paper,twocolumn,english]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{babel}
\usepackage[includeheadfoot,margin=2cm]{geometry}
\usepackage[font=small,labelfont=bf,tableposition=top]{caption}
\usepackage[font=footnotesize]{subcaption}
\usepackage{booktabs}
\usepackage{blindtext}

%\DeclareCaptionSubType*[arabic]{table}
%\captionsetup[subtable]{labelformat=simple,labelsep=colon}

\title{Two tables side by side in a \texttt{table*} environment within a two column document}
\author{Donatello}

\begin{document}
  \maketitle

  \blinddocument

  \begin{table*}
    \caption{Dummy tables}\label{tab:dummy}
    \centering
    \begin{subtable}[t]{\columnwidth}
      \caption{Dummy sub-table}\label{subtab-1:dummy}
      \centering
      \begin{tabular}{ccc}\toprule
        Table head & Table head & Table head \\ \midrule
        Some values & Some values & Some values \\
        Some values & Some values & Some values \\
        Some values & Some values & Some values \\ \bottomrule
      \end{tabular}
    \end{subtable}
    \hfill
    \begin{subtable}[t]{\columnwidth}
      \caption{Dummy sub-table}\label{subtab-2:dummy}
      \centering
      \begin{tabular}{ccc}\toprule
        Table head & Table head  & Table head\\ \midrule
        Some values & Some values & Some values \\
        Some values & Some values & Some values \\
        Some values & Some values & Some values \\ \bottomrule
      \end{tabular}
    \end{subtable}
  \end{table*}

  \blinddocument
\end{document}

I have chosen \columnwidth as width for the two subtable environments and centered the two sub-tables optically in the respective column.

The commented lines shall serve as a possible example for redefining the numbering of the subtables.

As always, the blindtext package is only for creating dummy text thus not part of the solution.