Yes, both foreigners and Russian citizens usually need a special permission to enter regions in Russia designated as border zones and Chukotka is one of them. On Google Street View, you can along the Finnish border find some of the signs indicating the start of the regulated border zone. This might sound as an odd, paranoid remnant from the communist era, but you will actually find a similar, though not so broad (up to 3km), border zone at the Finnish side of the border, for which you need a special permit to enter as well.
The Chukotka government offers a web page in English on the subject 'Entry permit issuance procedure', but the text is somewhat confusing and addresses the 'inviting party'. The thing is, that to obtain a border zone entry permit, you need a formal 'invitation' from a subject within the border zone and the government's information page seem to indicate that the inviting party must apply for the permit on your behalf. Such an 'invitation' is by the way even required for a regular Russian tourist visa and for tourists in most cases issued by a Russian tourist agency. Even if I can't find any tangible information, I would be pretty sure that you need assistance from a Chukotkan tourist agency for them to apply for an entry permit on your behalf.
On the web site visitchukotka.com, you can both find a list of tourist agencies and some details on the tours they offer.