A palette is a certain colour scheme used by an object, sprite, foreground, or background. A palette is not a background image or foreground tileset, but the colours these images and tilesets use.
Level Palette Editing
The palettes used in Super Mario World can be edited with Lunar Magic. Each level type (grassland, forest, castle, etc.) has eight preset foreground, background, and back area palette colours, though the option of creating custom palette colours can be done with the colours displayed on the left of the editing window. When a custom palette is created, it can be saved to the level itself through the Level>Enable Custom Palette option; the palette can also be saved to the ROM itself, that it might be used in other levels. Doing so overwrites one of the preset palette choices, but every level type has at least two or three 'bad' or undesirable palettes that can be easily overwritten.
Why edit palettes?
A good level is more than just obstacles and enemies; colours play a large part in how the level looks. After all, Super Mario World was never played in black-and-white.
When editing palettes, however, one often runs the risk of creating bad or clashing palettes. Levels with eye-searing colours that do not match are not fun to play and detract from the player's overall enjoyment of the hack. A smooth colour gradient and good colour combinations contribute positively to a level.
Overworld Palette Editing
Like levels, the Overworld and Submap palettes can be changed as well. This is useful in creating differently-themed sections of the Overworld (snowy, volcanic, and desert areas, for example). Unfortunately, one must be extremely careful when editing Overworld Palettes, as changing one colour can change more than what was intended. A common problem is when the switch blocks that shoot out of Switch Palaces after they have been cleared do not match the colour of the Palace, the switch, or both.
Title Screen Palette Editing
Similarly to the levels and Overworld, the title screen and demo level's palette can also be changed. This is useful when making custom titles and demo levels because it helps set one's hack apart from the original Super Mario World. As always, however, editing these palettes involves some risk. If the demo level palette is changed, the colour of the title screen's "File Select" text will often also change. This is not necessarily bad, but it is important to make sure that the player can read this text, as it is somewhat important.
Palette editing is a major aspect of SMW hacking, but it is always important to test out your colours before you rush to save them to the ROM. Too many good hacks are rejected because of bad palettes. Test and test again, and have someone else test the palette.