Here's one possibility redefining the headline template used by the PaloAlto theme; I defined a command \logoii to be used for the second logo in a fashion completely analogous to the standard \logo command (I used the same image for both logos in my example, but, of course, you can use whatever images you want instead):
\documentclass{beamer}
\usetheme{PaloAlto}
\makeatletter
\newcommand\insertlogoii{}
\newcommand\logoii[1]{\renewcommand\insertlogoii{#1}}
\setbeamertemplate{headline}
{%
\begin{beamercolorbox}[wd=\paperwidth]{frametitle}
\ifx\beamer@sidebarside\beamer@lefttext%
\else%
\hfill%
\fi%
\ifdim\beamer@sidebarwidth>0pt%
\usebeamercolor[bg]{logo}%
\vrule width\beamer@sidebarwidth height \beamer@headheight%
\hskip-\beamer@sidebarwidth%
\hbox to \beamer@sidebarwidth{\hss\vbox to
\beamer@headheight{\vss\hbox{\color{fg}\insertlogo}\vss}\hss}%
\hfill%
\vrule width\beamer@sidebarwidth height \beamer@headheight%
\hskip-\beamer@sidebarwidth%
\hbox to \beamer@sidebarwidth{\hss\vbox to
\beamer@headheight{\vss\hbox{\color{fg}\insertlogoii}\vss}\hss}%
\else%
\vrule width0pt height \beamer@headheight%
\fi%
\end{beamercolorbox}
}
\makeatother
\title{The Title}
\subtitle{CTAN lion drawing by Duane Bibby}
\author{The Author}
\logo{\includegraphics[height=0.8cm]{ctanlion}}
\logoii{\includegraphics[height=0.8cm]{ctanlion}}
\begin{document}
\begin{frame}
\maketitle
\end{frame}
\end{document}
