When a man cannot choose, he ceases to be a man.

So, the hidden messages... basically single lines of code in matlab...

The first one you might recognize by the artifacts at the four corners of the image, they suggest that something funny is going on in the frequency space. In other words the classic way to find the hidden message is to perform a 2D fourier transform on the image. Perhaps the simplest way to reveal the message is to use a gimp plugin (for example G'MIC). You can also make these images using G'MIC and simply painting your hidden messages and then inverse transforming them. However, I did mine in matlab. In this case I transform the red color component.

pic1 = imread('d:\babel\20131215\me.jpg');
imagesc(log10(abs(fft2(pic1(:, :, 1)))), [0 5]);
truesize;

The image suffers a little bit from jpg-compression, but no worries. The logarithmic scaling is unimportant, you see it just fine even with gimps default settings. You could use the same idea to encode messages into mp3s for example and they would be revealed in their spectrogram (4:10 is interesting in this video).

Perhaps the most famous was the face used by Aphex Twin at the end of one of their tracks (at 5:30).

Here's how I did my picture:

pic = imread('d:\babel\20131209\me.png');
MSG = imread('d:\babel\20131209\msg.png');
MSG = imresize(MSG, [406 640]);
R = fft2(pic(:, :, 1));
R = R + 15*double(MSG);
r = ifft2(R, 'symmetric');
pic(:, :, 1) = abs(r);
imwrite(pic, 'd:\babel\20131209\me.jpg', 'JPG');

You could do something similar even for a video.

The second image is a bit more interesting because no visible signs can be seen and it would be very difficult to recognize anything but noise even if you could compare it to the original unaltered image. Yet the method is fairly simple. The least significant bit of every pixel is part of 8-bit ASCII encoded message (notice how the image is encoded using a bit perfect PNG-compression unlike the first image).

pic2 = imread('d:\babel\20131215\cat.png');
sprintf(char(bin2dec(vec2mat(sprintf('%d', double(mod(pic2(1:1702*8), 2))), 8))))

ans =

You ask me...

Don't pay too much attention to the trickery in the code. There are numerous ways to do it all equally well. You could even encode the message into a lesser number of bits like 7 as ASCII is often encoded in or you could even make your own character sets or include further tricks, however I figured that doing so would make it unnecessarily hard. 

Through my living room window one early morning.

And here's the code to make the image with the message:

message = double('You ask me for a hamburger. My attempt to reciprocate is cut brutally short as my body experiences a sudden lack of electrons. Across a variety of hidden dimensions you are dismayed. John Lennon hands me an apple, but it slips through my fingers. I am reborn as an ocelot. You disapprove. A crack echoes through the universe in defiance of conventional physics as cosmological background noise shifts from randomness to a perfect A Flat. Children everywhere stop what they are doing and hum along in perfect pitch with the background radiation. Birds fall from the sky as the sun engulfs the earth. You hesitate momentarily before allowing yourself to assume the locus of all knowledge. Entropy crumbles as you peruse the information contained within the universe. A small library in Phoenix ceases to exist. You stumble under the weight of everythingness, Your mouth opens up to cry out, and collapses around your body before blinking you out of the spatial plane. You exist only within the fourth dimension. The fountainhead of all knowledge rolls along the ground and collides with a small dog. My head tastes sideways as spacetime is reestablished, you blink back into the corporeal world disoriented, only for me to hand you a hamburger as my body collapses under the strain of reconstitution. The universe has reasserted itself. A particular small dog is fed steak for the rest of its natural life. You die in a freak accident moments later, and you soul works at the returns desk for the Phoenix library. You disapprove. Your disapproval sends ripples through the inter-dimensional void between life and death. A small child begins to cry as he walks toward the stairway where his father stands.');

message_in_bin = dec2bin(message, 8);
A = imread('d:\babel\20131209\org_cat.png');
ss = size(message_in_bin);
message = message_in_bin';
for x = 1:ss(1)*ss(2)
    value = bin2dec(message(x));
    if mod(A(x), 2) ~= value
        if A(x) > 100
            A(x) = A(x) - 1;
        else
            A(x) = A(x) + 1;
        end
    end
end
imwrite(A, 'd:\babel\20131209\cat.png', 'PNG');

http://en.wikipedia.org/wiki/Steganography