Download the zipped plugin (the latest version will always be available at the WP MarkItUp! official page).
Unzip it and upload the whole wp_markitup directory to your /wp-content/plugins/ directory.
Make sure the permissions on all .php files it are at least 755. If you can SSH, simply go to the wp_markitup directory and type find . -name '*.php' | xargs chmod 755. Alternatively, just use any FTP client (Filezilla, Cyberduck) to do it manually.
Activate the plugin through the Plugins menu in WordPress.
Go to the WP MarkItUp! setting page under the Settings section. Here you can choose the toolbar and the skin to activate from the available ones.
There's no step six. Enjoy your brand new 21st century editor ;)