in reply to trying to match a greek phrase in a greek text
Well, maybe if your provide link to the page, then it would be easier to say, what should you do.
In general, the locale does not make much difference. More important is to know which encoding is used by the HTML document you get. It can be in UTF-8, or in UTF-16, or even iso-8859-7. Knowing the encoding of the document you shall convert the text from the page into "perl's encoding". This is done using Encode module, specifically with Encode::decode(ENCODING, $text). After that you can apply to the resulting text your regular expressions.
Another important note. When writing your regular expressions, you put into them greek letters. So, now your own program also contains letters in some encoding. The encoding of the program depends on the editor (and possibly locale). If your editor saves everything in UTF-8 (default on Linux), then you can simply specify "use utf8;" to tell perl that the text in regular expressions is encoded using UTF-8 locale, then perl automatically converts them to "perl's encoding" before matching.