Warning: answer contains MASSIVE unmarked spoilers!
Lack of surprise fits with the process he's going through.
After Shadow dies on the tree, his entire experience in the succeeding chapters is a surreal journey of enlightenment and oblivion. He forgets real-world things like his name, and learns so much more (which he soon forgets after coming back to life).
"Do you remember?" she asked. "Do you remember what you learned?"
"I lost my name, and I lost my heart. And you brought me back."
-- Easter and Shadow, Chapter 19
"You learn anythin' from all this?"
Shadow shrugged. "I don't know. Most of what I learned on the tree I've already forgotten," he said. "I think I met some people. But I'm not certain of anything anymore. It's like one of those dreams that changes you. You keep some of the dream forever, and you know things deep down inside yourself, because it happened to you, but when you go looking for details they kind of just slip out of your head."
"Yeah," said Mr. Nancy. And then he said, grudgingly, "You're not so dumb."
"Maybe not," said Shadow. "But I wish I could have kept more of what passed through my hands, since I got out of prison. I was given so many things, and I lost them again."
"Maybe," said Mr. Nancy, "you kept more than you think."
"No," said Shadow.
-- Nancy and Shadow, Chapter 20
The fact that he shows no surprise at learning that Wednesday is his father might be a foreshadowing of his experience further along his journey, where he learns about death, and gods, and (it is suggested) the fundamentals of the universe, as he passes into nothingness. As he moves further into the realm of death, his enlightenment and inability to be surprised increase.
Also, he's already figured out the grand master plan.
"I figured it out," said Shadow. "Kind of. I'm not sure when I figured it out. Maybe when I was hanging on the tree. Maybe before. It was from something Wednesday said to me, at Christmas."
Loki just stared at him from the floor, saying nothing.
"It's just a two-man con," said Shadow. "Like the bishop with the diamond necklace and the cop who arrests him. Like the guy with the fiddle, and the guy who wants to buy the fiddle. Two men, who appear to be on opposite sides, playing the same game."
-- Shadow and Loki, Chapter 19
He'd already realised, or is in the process of realising what the whole Old vs New Gods war is really all about, either while he was on the tree or even before. Given that the whole thing is a con job cooked up by Odin and Loki, Shadow must be wondering what his own place in all this is.
It's unlikely that any of the plan is a coincidence, so the fact that Wednesday hired him, (apparently) an ordinary mortal human, and brought him into the world of gods, is probably less of an accident than it seemed. Perhaps he's already realised that Wednesday needed someone to die for him. Perhaps he's begun to wonder, "why me?" Given how deeply involved with the world of gods he's become in so short a time, it shouldn't really be a surprise that his involvement actually goes back much further.
Besides, it's no surprise to us
, right? Whenever a character in literature has a 'mystery father', it usually turns out to actually be some other character in the book. And nobody would fit better than Wednesday, the man who hired Shadow and looked after him and brought him into the world of gods. Well, Shadow used to read a lot of fiction too - perhaps, in some sort of meta sense, he's unsurprised for just the same reason we are.