weird permalinks!?

Hi,

I’ve set up a new WordPress instance. Everything seems to work alright but the permalinks look odd: mydomain.com/index.php/contact, mydomain.com/index.php/info, etc instead of mydomain.com/contact, mydomain.com/info …

How did that happen and how can I correct this?

Thanks!