Hi Maverek,
Visit PSK of your area ASAP.
No need to get new passport.
Apply for yourself and your spouse online with below important points:
1) For your spouse give address of both the places, pre marriage and post marriage with duration and time period
2) Get a bank account opened in a nationailised bank, just one day job and get a passbook handy with names and current address of both on it.
3) Keep marriage certificate handy ..
Visit PSK as in case of adverse report, you will have to go through a police verification which takes a month. So be quick and as soon as your police verification is done, visit passport office for a status as PSK website does not update status so frequently...
If you are applying from Delhi, then you can straightaway apply for PCC on Delhi police website and that will be available online in a week, if you are applying from rest of india, PSK or passport office is the only solution.
Hope this helps