Что надо делать сначала, регистрировать домен или заказывать хостинг?

Последовательность не важна. Да и частенько при заказе хостинга вам могут выделить домен 3 уровня бесплатно.

проверить, не занято ли такое имя уже

1. Проверить предполагаемое доменное имя (свободное или аукционное) на историю, баны, агс.
2. Если имя красивое и без "косяков" - стоит сразу зарегистрировать в том же nic.ru и иже с ними (У хостера, мол домен в подарок, регить не стоит - если сайт будет развиваться и будете уходить на другой хостинг, при работе с недобросовестным хостером, намучаетесь выковыривать домен - а у вас уже и тиц на нем будет, и ссылки на него... )
Если имя так себе, то и регистрировать смысла нет, пока не сверстаете/проверите ваш сайт.

Продумать тематику сайта, сверстать, проверить на локальной машине/сервере.

А вот после этого уже заказывать хостинг с необходимыми хар-ками и прописывать для вашего доменного имени dns.

Это для минимальных затрат и более правильно с точки зрения оформления.

Если не "заморачиватся" - заказать какой-нибудь простенький хостинг - большинство хостеров дарят домен при оплате за полгода/год (зависит от тарифного плана).

И то и другое одновременно, причем если не хотите заморачиваться с привязкой домена к хостингу, то делать это у одной компании, например
этой.

Не важно что вы арендуете первым, у меня это был хостинг от http://sartelekom.ru/ а потом уже домен.