The fact that you're newlywed is irrelevant. What is important is that you are one family travelling together.
I've been in exact this situation before. I am an American citizen and my wife is not. Whenever we fly to the USA, we'd go through the immigration together - through the lanes for "Non-US passports". We give two passports together - mine and hers (with the visa). The agent usually checks her details first, get her fingerprint scan, then quickly scans my passport, says something like "Welcome home" - and we're in.
That said, last time we flew to the USA was about a year ago. Furthermore, different airports may have different policies regarding this. We usually fly to BOS (Boston Logan) and once to New York (JFK).
I do think though that you should be fine going together, but make sure to go via the "non-US passports" lanes.