Use \framebox instead of \fbox.
\begin{figure}
\centering
\framebox[1\linewidth][t]{%
\begin{minipage}[t]{0.48\linewidth}%
\begin{minipage}[t]{1\linewidth}%
left part is going to be very big sentence that goes into two lines
\end{minipage}%
\end{minipage}\hfill
\begin{minipage}[t]{0.48\linewidth}%
\begin{minipage}[t]{1\linewidth}%
right part is going to be very big sentence that goes into two lines
\end{minipage}%
\end{minipage}}%
\captionof{figure}{An example program}\label{fig:An example program}
\end{figure}

EDIT: As per Martin's comments on using \framebox and verbatim text/catcode changing material, this code will work as desired using \fbox
\begin{figure}
\centering
\fbox{%
\begin{minipage}[t]{1\linewidth-2\fboxsep-2\fboxrule}%
\begin{minipage}[t]{0.48\linewidth}%
left part right part is going to be very big sentence that goes into two lines
\end{minipage}\hfill
\begin{minipage}[t]{0.48\linewidth}%
right part right part is going to be very big sentence that goes into two lines
\end{minipage}
\end{minipage}}
\captionof{figure}{An example program}\label{fig:An example program}
\end{figure}
However, you have to use
\usepackage{calc} % as per Stephan's advice.
for this to work properly.
PS. If you want this to go up to the paper width (do you really want to do that?), you have to reduce the margins to zero using geometry.
I am of the opinion that you can simply use \caption inside figure environment (instead of \captionof which will be used outside \figure environment)

0.48to0.5? – Roelof Spijker Mar 22 '12 at 16:04%after the trailing{of\fboxto avoid a space being inserted here by the end-of-line character. This will give you some extra whitespace at the left of the border. – Martin Scharrer♦ Mar 22 '12 at 16:19\captionof{figure}insidefigure. Just use\caption. – Martin Scharrer♦ Mar 22 '12 at 16:21