Step 1: Download a launcher
Go to the Google Play Store and choose a launcher to your liking. Launchers are apps that modify the Android user interface. These range from the more powerful home launchers (system-level customization) and OS launchers (takes the skin/behavior of other operating systems.
—e.g., iOS and Windows Phone) to theme launchers (easy home screen customization). Your top options include Nova Launcher, GO Launcher, Espier Launcher, Themer, and Buzz Launcher. Try one and see if it fits your needs.
I enjoy themes, so my personal preference is Buzz Launcher. Like other theme launchers, it doesn't dive in too deep into the OS. What Buzz Launcher focuses on is home-screen themes. It provides an automatic setup, wherein you just choose a theme/home screen and the launcher takes care of most of the settings.
Step 2: Choose a theme
Most launchers have a cloud database of themes that you can download and install on your mobile device. A Home pack is a package of home screen wallpaper and app icons. You get access to different home screen styles from tiles (a la Windows Phone) to typography. If you just want to replace your app icons, icon packs are there for you.
Step 3: Set custom widgets
Most launchers offer custom widgets. In fact, many if not all of them support ultimate custom widgets or UCCW and have themes that already use them. These widgets take customization right in your hands because you can actually create your own widgets and the icons that you wish to attach to them. That is, you can install a widget, set actions, customize its appearance, and assign your very own icon.