Где мне нужно получать разрешение на работу если я гр. Украины и собираюсь работать в России???

Лучше всего зайти на сайт Миграционной службы РФ и прочитать все документы там. Кроме разрешения, нужно еще документ о сдаче экзамена на знание русского языка и истории. Это есть отдельное отделение в Москве в Университете дружбы народов. Где в других городах, не знаю. Разрешения на работу выдаются по квоте, т. е. , например, каждому региону выдается определенное количество разрешений, которые они могут оформить в течение года. В Москве в 2012г. было разрешено оформить 250 тыс. человек. И так, в каждом регионе. Но для граждан Украины раньше были какие-то льготы. Как сейчас не знаю. Но для всех иностранцев система такая: разрешение (по квоте) на работу, документ о регистрации (где будешь жить) , документ о сдаче экзамена на знание русского языка. Смотри и задавай вопросы в Миграционную службу или в Посольство РФ в Украине.

поправлю господина Александра, писавшего о гастербайтерах.. .

подобной чуши Путин никогда НЕ подписывал.. .
..изменения в законе касаются исключительно иностранных граждан, имеющих РВП (разрешение на временное проживание), теперь им разрешение на работу оформлять не нужно (хотя закон в силу ещё не вступил). .
..замечу, что подобная норма была в законе несколько лет назад, но была исключена, теперь снова восстановлена...

Путин подписал закон, согласно которому гастарбайтеры смогут работать в РФ без разрешения на работу. Но никто этого не заметил на фоне гражданства для Депардье

Одновременно с предоставлением российского паспорта французскому актёру Президент Путин подписал закон «О внесении изменений в Федеральный закон «О правовом положении иностранных граждан в Российской Федерации» . Согласно этим изменениям, «работодателям и заказчикам работ предоставляется право привлекать и использовать для осуществления трудовой деятельности иностранных работников, временно проживающих в Российской Федерации, без наличия разрешения на привлечение и использование иностранных работников. Одновременно указанной категории иностранных граждан предоставляется право осуществлять трудовую деятельность без разрешения на работу» .

Теперь любая строительная компания (к примеру) для того, чтобы нанять себе на работу очередную сотню таджиков, больше не должна будет морочиться с оформлением разрешения на «привлечение иностранных работников» . В свою очередь, и эти таджики спокойно смогут обходиться без разрешения на работу. Им теперь достаточно просто въехать на территорию РФ — и всё. Ну, может, еще оформить временную регистрацию. И можно устраиваться на работу на тех же основаниях, что и граждане нашей страны.

Не путайте человека!

Вам нужно обратиться в орган ФМС в сфере трудовой миграции. в Питере это Единый Мигрционный центр

Посмотрите сайт Федеральной Миграционной Службы России. Там очень хорошо описан порядок получения разрешения на работу.
http://www.fms.gov.ru/documents/withoutvisa/