How to add a picture to fancyhdr *header* (and align in the top right)?

Don't use picture but instead directly use \includegraphics:

\rhead{\includegraphics[width=1cm]{example-image-a}}

Now you should get a warning by fancyhdr about headheight:

Package Fancyhdr Warning: \headheight is too small (12.0pt): 
 Make it at least 24.93825pt.
 We now make it that large for the rest of the document.
 This may cause the page layout to be inconsistent, however.

To get rid of this, add:

\setlength\headheight{26pt} 

to the preamble. _{This can be better done with the help of geometry package. That is a different story.}

So the code will be:

\documentclass[a4paper]{article}

\usepackage{graphicx}

\usepackage{fancyhdr}
\pagestyle{fancy}

\usepackage{xcolor}

\usepackage{lipsum}
\setlength\headheight{26pt} %% just to make warning go away. Adjust the value after looking into the warning.
% \rhead{{\color{blue}\rule{1cm}{1cm}}}

\rhead{\includegraphics[width=1cm]{example-image-a}}

% \rhead{\begin{picture}(3,3) \put(3,3){\includegraphics[width=1cm]{example-image-a}} \end{picture}}

\begin{document}

\lipsum

\end{document}

In addition to Harish's answer, I recommend using the geometry package.

\usepackage[margin=2.5cm,headheight=26pt,includeheadfoot]{geometry}

The crucial points are setting headheight to a value bigger than the one in the warning (and omitting the \setlength\headheight command) and includeheadfoot if you use a footer at the same time.

Further details can be found here and here.