Interpolation is 'digital interpretation' - whether this is interpreting film scanned into digital, or the manipulation of digitally-generated image files, there's always a loss or degrading of information.
Anti-aliasing due to image remapping
These artefacts are impossible to completely avoid when resizing, sharpening or remapping, but you can help by avoiding excessively working and re-working an image, as will correct sharpening and due consideration to file size.
To understand interpolation, you need to understand why seemingly logical processes don't work as you may expect due to digital sampling. Because as digital is made to 'imitate' its analogue counterpart, there's a limitation to the equivalent level of 'accuracy' that this can occur.
Anti-Aliasing
A crude example of anti-aliasing effects would be to take a black pen to a piece of paper and draw a diagonal line. Do the same in a digital form and you are limited to pixels - where the values of black (pen) or white (paper) can only either be 'off' or 'on'. This digital representation does not have an unlimited capacity whereby the line transects a pixel; as this is not possible:

Caption: Digital representation of 'analogue' diagonal line.
Almost all cameras now use an anti-aliasing filter in order to 'lessen' this problem - the filter diffuses light in order for more sensor nodes to capture surrounding information. However, the very process of anti-aliasing further softens edges within an image.

Caption: Anti-aliased digital representation of 'analogue' diagonal line.
Detail loss also occurs with image resizing. Imagine that Photoshop needs to 'reduce' the information present in an original file to make a smaller version.
Lets say the original file is 3000x2000pixels (at 300dpi), but you only need it to be 1500x1000pixels (at 300dpi). By resizing the image you don't want to simply lose half the lines of pixels information - you wish to retain the same structure and proportion of image, though only at a smaller (therefore less detailed) scale. May sound simple, but is actually a complex calculation to reduce loss of detail. Photoshop needs to do its sums on this sort of job, so the resized image is more a representation of the original than anything else - often finding a medium between adjacent pixels and generating a new colour value that is neither of the original two but a calculated mid-point of the two. (see BiCubic Interpolation).
Here's a very crude example that you could assert upon image resizing. A series of black and white vertical lines, each 1 pixel wide is to be halved in size. Rather than maintaining the black lines, PhotoShop will make a judgement on the value of the black against the white and conclude a mid grey.

Caption: Black and white lines, 1 pixel wide. Viewed at +400% to demonstrate.

Caption: Original image is resized to 50% of original. Through such process, Photoshop makes adjustments to compensate, resulting in a series of grey - essentially a “soft” version of the original. Viewed at +800% to demonstrate (as equal size of 1st image).
Remapping & Resizing - What's the difference?
Resizing is where the physical (pixel) size changes, so information is lost and therefore interpolated as an appropriate value. Remapping is either where the physical size changes but through the process of distortion, or the same pixels are taken and mapped out elsewhere (such as through a 45° rotation).
Repetitious transformations that logically (in an analogue sense) wouldn't cause issues, er, cause issues digitally - in the form of Interpolation Artefacts. For example, if you were to place a £5 note on the table in front of you and proceed to rotate in 45° at a time through a full circle, it would still be the same £5 note at the end. Apply the same process to a digital image file and the initial straight edge becomes a 45° anti-aliased decline. Continue to repeat the rotation and the sampling and resampling digs itself into a deeper hole each time - the same sampling method is being utilised and the quality of the results decreases through reiteration. Therefore the final result will eventually become entirely soft and beyond repair.
Another common issue with remapping is trying to generate information from nothing - if a distortion is made where there is any form of enlargement, Photoshop will calculate the pixels to add. Of course, this is best guessing (albeit 'accurate guessing') and the results tend to be blurred - a common interpolation artefact.
Enlargement / Upscaling
Those used to shooting film will know that the process of enlargement is important, if not limited. Digital 'negatives' are at full size when they are taken, so to enlarge them would be asking more information to be created from 'nothing'. Therefore softness occurs - another interpolation artefact form. But, like with film, the bigger your original 'negative' the more detail there is and therefore (theoretically) the more detail that will be retained through enlargement (this is theoretical however because issues such as image noise will interfere with the potential amount of detail).
Stock sites - citing Alamy in particular here - require images to be 48MB+ TIFFs. If your image isn't 48MB then the company advises that you "interpolate (upsize) the file to at least 48MB using a specialist, professional software package (Genuine Fractals or Photoshop 7 or higher)". There's a distinct reason that Photoshop 7 or above is mentioned, and this is to do with the type of interpolation:
BiCubic Interpolation: (available from PhotoShop 7 and above)
The bigger brother of BiLinear interpolation. The best way to think about it is that, for the process of enlargement, a new set of pixels need to be generated. In the case of single pixels, BiLinear interpolation uses the surrounding 2x2 pixel grid (4 pixels) to make an average value (the new pixel).
BiCubic steps things up a notch, using the surrounding 4x4 pixel grid (16 pixels) to make an average value (the new pixel). The closer pixels are given a higher weighting of value than those further away, but all are used to perform the calculation.
Phew. There's a whole lot of info to know before you can rock it like a pro. Keep at it, and ThinkCamera looks to guide you on your merry way. Any questions or queries, raise them in the forum and we shall do our 'most bestest' the answer them in the usual manner.
And then there's Photoshop CS4 expected soon... Which, who knows, could change things even more!