How does hardware texture compression work? That it compresses the data compared to the pixel array is obvious.

But what makes it different from from normal compression (like png, jpeg)?
"How (hardware) texture compression works" is a large topic. Hopefully I can provide some insights without duplicating the content of Nathan's answer.

Requirements

Texture compression typically differs from 'standard' image compression techniques e.g. JPEG/PNG in four main ways, as outlined in Beers et al's Rendering from Compressed Textures:


Decoding Speed: You don't want texture compression to be slower (at least not noticeably so) than using uncompressed textures. It should also be relatively simple to decompress since that can help achieve fast decompression without excessive hardware and power costs.
Random Access: You can't easily predict which texels will be required during a given render. If some subset, M, of the accessed texels come from, say, the middle of the image, it's essential that you don't have to decode all of the 'previous' lines of the texture in order to determine M; with JPEG and PNG this is necessary as pixel decoding depends on the previously decoded data.
Note, having said this, just because you have "random" access, doesn't mean you should try to sample completely arbitrarily
Compression Rate and Visual Quality: Beers et al argue (convincingly) that losing some quality in the compressed result in order to improve compression rate is a worthwhile trade-off. In 3D rendering, the data is probably going to be manipulated (e.g. filtered &amp; shaded etc) and so some loss of quality may well be masked.
Asymmetric encoding/decoding: Though perhaps slightly more contentious, they argue that it is acceptable to have the encoding process much slower than the decoding. Given that the decoding needs to be at HW fill rates, this is generally acceptable. (I will admit that compression of PVRTC, ETC2 and some others at maximum quality could be faster)


Early History &amp; Techniques

It may surprise some to learn that texture compression has been around for over three decades. Flight simulators from the 70s and 80s needed access to relatively large amounts of texture data and given that 1MB of RAM in 1980 was > $6000, reducing the texture footprint was essential. As another example, in the mid 70s, even a small amount of high speed memory and logic, e.g. enough for a modest 512x512 RGB frame buffer) could set you back the price of small house.

Though, AFAIK, not explicitly referred to as texture compression, in the literature and patents you can find references to techniques including:
 a. simple forms of mathematical/procedural texture synthesis,
 b. use of a single channel texture (e.g. 4bpp) that is then multiplied by a per-texture RGB value,
 c. YUV, and
 d. palettes (the literature suggesting use of Heckbert's approach to do the compression) 

Modelling Image Data

As noted above, texture compression is nearly always lossy and thus the problem becomes one of trying to represent the important data in a compact way whilst disposing of the less significant information. The various schemes that will be described below all have an implicit 'parameterised' model that approximates the typical behaviour of texture data and of the eye's response. 

Further, since texture compression tends to use fixed-rate encoding, the compression process usually includes a search step to find the set of parameters which, when fed in to the model, will generate a good approximation of the original texture. That search step, however, can be time consuming.
(With the possible exception of tools such as optipng, this is another area where typical use of PNG &amp; JPEG differ from texture compression schemes)

Before progressing further, to help with further understanding of TC it's worth taking a look at Principal Component Analysis (PCA) - a very useful mathematical tool for data compression.

Example texture

To compare the various methods, we'll use the following image:


Note that this is a fairly tough image, especially for palette and VQTC methods as it spans much of the RGB colour cube and only 15% of the texels use repeated colours.

PC and (post mid 90s) Console Texture compression

To reduce data costs, some PC games and early games consoles also made use of palette images, which is a form of Vector Quantisation (VQ).
Palette-based approaches make the assumption that a given image only uses relatively small portions of the RGB(A) colour cube.  A problem with palette textures is that the compression rates for the achieved quality is generally rather modest. The example texture compressed to "4bpp" (using GIMP) produced

Note again that this is a relatively tough image for VQ schemes.

VQ with larger vectors (e.g. 2bpp ARGB)

Inspired by Beers et al, the Dreamcast console used VQ to encode 2x2  or even 2x4 pixel blocks with single bytes. While the "vectors" in the palette textures are 3 or 4 dimensional, the 2x2 pixel blocks can be considered to be 16 dimensional. The compression scheme assumes there is sufficient, approximate repetition of these vectors. 

Even though VQ can achieve satisfactory quality with ~2bpp, the problem with these schemes is that it requires dependent memory reads: An initial read from the index map to determine the code for the pixel is followed by a second to actually fetch the pixel data associated with that code. Additional caches can help alleviate some of the incurred latency, but adds complexity to the hardware.

The example image compressed with the 2bpp Dreamcast scheme is 
. 
The index map is: 

Compression of VQ data can be done in various ways however, IIRC, the above was done using PCA to derive and then partition the 16D vectors along the principal vector into 2 sets such that two representative vectors minimised the mean squared error. The process then recursed until 256 candidate vectors were produced. 
A global k-means/Lloyd's algorithm approach was then applied to improve the representatives.

Colour Space Transformations

Colour space transformations also make use of PCA noting that the global distribution of colour is often spread along a major axis with far less spread along the other axes. For YUV representations, the assumptions are that a) the major axis is often in the luma direction and that b) the eye is more sensitive to changes in this direction.

The 3dfx Voodoo system provided "YAB", an 8bpp, "Narrow Channel" compression system that split each 8 bit texel into a 322 format, and applied a user selected colour transform to that data to map it into RGB. The main axis thus had 8 levels and the smaller axes, 4 each.

The S3 Virge chip had a slightly simpler, 4bpp, scheme that allowed the user to specify, for the entire texture, two end colours, which should lie on the principal axis, along with a 4bpp monochrome texture. The per-pixel value then blended the end colours with appropriate weights to produce the RGB result.

BTC-based schemes

Rewinding some number of years, Delp and Mitchell designed a simple (monochrome) image compression scheme called Block Truncation Coding, (BTC). This paper also included a compression algorithm but, for our purposes, we are mainly interested in the resulting compressed data and of the decompression process.  

In this scheme, images are broken into, typically, 4x4 pixel blocks, which can be compressed independently with, in effect, a localised VQ algorithm. Each block is represented by two "values", a and b, and a 4x4 set of index bits, which identify which of the two values to use for each pixel.

S3TC:  4bpp RGB (+1bit alpha)
Although several colour-variants of BTC for image compression were proposed, of interest to us is Iourcha et al's S3TC, some of which appears to be a rediscovery of the somewhat forgotten work of Hoffert et al that was used in Apple's Quicktime.

The original S3TC, without the DirectX variants, compresses blocks of either RGB or RGB+1bit Alpha to 4bpp. Each 4x4 block in the texture is replaced by two end colours, A and B, from which up to two other colours are derived by fixed-weight, linear blends. Further, each texel in the block has a 2-bit index that determines how to select one of these four colours. 

For example the following is a 4x4 pixel section of the test image compressed with the AMD/ATI Compressenator tool. (Technically it's taken from a 512x512 version of the test image but forgive my lack of time to update the examples).

This illustrates the compression process: The average and the principal axis of the colours are calculated.  A best fit is then performed to find two end points that 'lie on' the axis which, along with the two derived 1:2 and 2:1 blends (or in some cases a 50:50 blend) of those end points, that minimises the error.  Each original pixel is then mapped to one of those colours to produce the result.

If, as in this case, the colours are reasonable approximated by the principal axis, the error will be relatively low. However if, like in the neighbouring 4x4 block shown below, the colours are more diverse, the error will be higher.
  

The example image, compressed with the AMD Compressonator produces:
  

Since the colours are determined independently per-block, there can be discontinuities at block boundaries but, as long as the resolution is kept sufficiently high, these block artefacts may go unnoticed:


ETC1:  4bpp RGB
Ericsson Texture Compression also works with 4x4 blocks of texels but makes the assumption that, much like YUV, the principal axis of a local set of texels is often very strongly correlated with "luma". The set of texels can then be represented by just an average colour and a highly quantised, scalar 'length' of the projection of the texels onto that assumed axis.  

Since this reduces the data storage costs relative to say, S3TC, it allows ETC to introduce a partitioning scheme, whereby the 4x4 block is subdivided into a pair of horizontal 4x2 or vertical 2x4 sub-blocks. These each have their own average colour. 
The example image produces:

The area around the beak also illustrates the horizontal and vertical partitioning of the 4x4 blocks.
    

Global+Local

There are some texture compression systems that are a cross between global and local schemes, such as that of the distributed palettes of Ivanov and Kuzmin or the method of PVRTC.  

PVRTC:  4 &amp; 2 bpp RGBA
PVRTC assumes that an (in practice, bilinearly) upscaled image is a good approximation to the full-resolution target and that the difference between the approximation and the target, i.e. the delta image, is locally monochromatic, i.e. has a dominant principal axis. Further, it assumes the local principal axis can be interpolated across the image.

(to do: Add images showing breakdown)

The example texture, compressed with PVRTC1 4bpp produces:

with the area around the beak:

Compared to BTC-schemes, the block artefacts typically are eliminated but there can sometimes be "overshoot" if there are strong discontinuities in the source image, for example around the silhouette of the lorikeet's head.

The 2bpp variant has, naturally, higher error than the 4bpp (note loss of precision around the blue, high frequency areas near the neck) but arguably still of reasonably quality:


A note on decompression costs

Although the compression algorithms for the schemes described above have a moderate to high evaluation cost, the decompression algorithms, especially for hardware implementations, are relatively inexpensive. ETC1, for example, requires little more than a few MUXes and low-precision adders; S3TC effectively slightly more addition units to perform the blending; and PVRTC, slightly more again.  In theory, these simple TC schemes could allow a GPU architecture to avoid decompression until just prior to the filtering stage, thus maximising the effectiveness of internal caches.

Other Schemes

Other common TC modes that should be mentioned are:


ETC2 - is a (4bpp) superset of ETC1 that improves the handling of regions with colour distributions that don't align well with 'luma'. There are also a 4bpp variant that supports 1 bit alpha, and an 8bpp format for RGBA.
ATC - Is effectively a small variation on S3TC.  
FXT1 (3dfx) was a more ambitious variant of the S3TC theme.
BC6 &amp; BC7 : An 8bpp, block-based system supporting ARGB. Apart from HDR modes, these use a more complex partitioning system than that of ETC to attempt to better model image colour distribution.
PVRTC2 : 2&amp;4bpp ARGB. This introduces additional modes including one to overcome limitations with strong boundaries in the images.
ASTC : This is also a block based system but is somewhat more complicated in that it has a large number of possible block sizes targeting a wide range of bpp. It also includes features such as up to 4 partition regions with a pseudo-random partition generator, and variable resolution for the index data and/or colour precision and colour models.