Well, there're 2 kinds of tilesets.

So, here goes the wall of text.
Character set = a look of all characters (beds, walls, letters etc.).
Graphic set = a look of  creatures.

A character set is used to represent actual ASCII tiles in game.
Most of the symbols from it are hardcoded (beds, gems, walls, hatches etc.) and some users even change some letters to pictures for the things indicated with letters to look like objects, i.e. wall corner ('O' tile) but it leads to weird names with pictures instead of letters.

The look of mineral tiles (displayed on unmined stone walls like "%" for microcline), tiles of trees/plants and tiles of creatures can be changed.
In their description (soils, trees, plants, creatures) there's a token [TILE:] which allows you to change the look of them.
-If you use a number in it, i.e. [TILE:154] it will use the tile from CHARACTER set #154. Remember that tiles are counted from left to right and from top to bottom in lines, like you read a book, but also remember that the first tile has the number 0 (not 1).
-If you use '' you can set a keyboard symbol, i.e. [TILE:'o'] will mean that the thing will have "o" letter as a tile.
Also colors are determined with [COLOR:A:B:C] token, where A = color, B = background color and C = brightness (actually 0 or 1 which means dark or bright). http://www.dwarffortresswiki.net/index.php/Color

And there's a special support for creature tiles. The creatures (and creatures only) can be replaced with pixel images. Firstly note that in your /data/init/init.txt there's [GRAPHICS:YES] not the [GRAPHICS:NO].

In /raw/graphics/ folder there are text files which determine it.
There's already graphics_example.txt file.
Let's look into the one from a graphic tileset.

00: graphics_example                 // the name of the file without the extension (.txt)
01:                                         // empty line
02: [OBJECT:GRAPHICS]             // every raw file has [OBJECT:] definition which tells the game what goes into this file. This one has graphics.
03:                                         // empty line
04: [TILE_PAGE:DWARVES]         // this means that we want to add an image file with dwarves' pictures and we call it DWARVES
05: [FILE:example/dwarves.bmp] // the location of the file (folder /example, file dwarves.bmp)
06: [TILE_DIM:16:16]                // the size of a tile for a creature inside bmp, 16x16 pixels here (Tile_dimesion(x)=16; Tile_dimension(y)=16)
07: [PAGE_DIM:9:22]                // the number of tiles, 9x and 22y (horizontal X vertical). The image size counts as [x*Tile_dim(x); y*Tile_dim(y)]
08:                                       // empty line
09: [CREATURE_GRAPHICS:DWARF]  // determines which creature will be described now
10: [DEFAULT:DWARVES:0:0:ADD_COLOR] // DEFAULT type image, the basic dwarven picture
11: [MINER:DWARVES:1:0:AS_IS:DEFAULT] // MINER profession image
12: etc.

Explanation of:
[MINER:DWARVES:1:0:AS_IS:DEFAULT]
MINER = profession for which the image is used
the possible professions are

DWARVES - the TILE_PAGE which we use to find this image, basically there can be more than one TILE_PAGE in 1 file (look at the string 04) and here we show that we look into file which we announced as "DWARVES".

:1:0: the position of the tile on the full image, x=1 and y = 0. Note that the first tile has not 1:1 but 0:0 coordinates.

AS_IS - uh, I don't know, I have never seen it changed.

DEFAULT - "texture"; the last parameter is used to define the "role".
It can be
So your "wrestler" may be DEFAULT, GUARD, ROYALGUARD or CASTLEGUARD.
Also the dog may be DEFAULT, SKELETON or ZOMBIE


Another note.
You can have more than one txt file for such descriptions if you want, i.e. you may want to have graphics_humans.txt for different humans, graphics_animals.txt for different animals etc.
The file structure should be the same.
Firstly the filename without the extension, then OBJECT:GRAPHICS token, then determination of TILE_PAGEs you want to use and then the description of creatures.

Also you may want to use an already prepacked version if it seems to hard or you don't want to spend your time on it, however I suggest you to try to get into it, it's much funnier to play with all the things as you want.

Prepacked versions of 39c with graphics:
http://dffd.wimbli.com/file.php?id=62

I'd like to know that too, I'm having a hell of a time getting Mayday to work completely with 39e.

What do you mean, altered tilesets? You don't need to alter tilesets for new versions of DF... You can just copy the needed files over to the new version and they'll work fine (as long as the init.txt is also set properly and all that).

Here's what I usually do:

• Extract the new version of DF into a new folder, like C:\Games\Dwarf Fortress 28.181.39e. The old version that time was C:\Games\Dwarf Fortress 28.181.39d of course. I'm going to refer to these as 'new' and 'old' from now on, for simplicity.
  
• Open up old/data/art and copy your font bmp (e.g. GuybrushASCII_curses_square_16x16.bmp or whatever) into new/data/art.
  
• Delete everything in new/raw/graphics.
  
• Copy everything from old/raw/graphics folder into new/raw/graphics
  
• Merge the settings from your old init.txt into the new one (I'd recommend using WinMerge if you're on windows). If the text goes all FUBAR when you try to scroll, get WinMerge 2.6.14 instead. There was some kind of stupid bug introduced in a version after that which was still around in 2.8, and after trying half a dozen versions to get back to one that worked, I haven't bothered trying the new versions to see if they've fixed it.
  

Or, perhaps someone could link me to this thing that you're saying you can't get working. Maybe it's more complicated than this and mods some of the raws - in which case it could be turned into a ModBase mod.

P.S. Nevermind about sending me a link to it, I found it, when I actually got around to checking http://www.dwarffortresswiki.net/index.php/List_of_user_graphics_sets , but Mike Mayday's website's download link for it says "Get the latest version HERE! (v9, updated 26 VII 2008)" and the file it links to doesn't actually exist. (The v8 file still exists though. It looks like it should still work if you do what I said and do what that other thread says. I'm a bit surprised he would have gone and changed the interface keys, though.)

On the creature tileset page, the "AS_IS" part can be changed to "ADD_COLOR." If you do that, your image will have all the non-pink areas be colored with whatever DF is set to color the tile with (Carpenters will be yellow, nobles will be purple, Miners will be grey, ect.). I have no idea why you would want to do this except maybe to give dwarves a default image, like the one Toady drew, then set it to "ADD_COLOR", just so everything has a picture.

Not to mention the rivers made of bricks on the overland map...