If by omniscience you mean the ability to know everything about the future as well as the past in our current universe, then determinism would make such a creature simpler to conceive. Such a creature would not need to know everything about the universe per se; it would need to know the exact starting position of the universe, and the rules under which the determinism works, then from first principles anything within the universe at any given time could be predicted through a complete model of the universe inside such a creature's mind.
Of course, being able to conceive so much information and run through that much processing to determine the information that's needed at any given point probably makes such a creature incapable of residing inside our universe because such a 1:1 model ceases to be a model and becomes a replica contained within the mind of the creature, meaning that the creature itself by definition would have to be larger than our own universe.
Models exist as simplifications of reality for this very reason; they allow us to predict specific actions or behaviours within a given context without having to understand or recreate the entire universe. As such, another possibility remains. A creature who only appears to be omniscient.
From our perspective the universe is so large that we can't even see its entirety. Scientists often refer to the observable universe as that part of the universe that it is possible to know. Therefore, it's possible to have a creature that simply knows more than we do (a superset, not overlapping set) and that knows that body of information that we can conceive of asking. Being able to answer any question we can think of would make such a creature appear omniscient to us, but it could still reside in our given universe.
Of course (combatibilism notwithstanding) if we assume that determinism is NOT the case and that we have open choices, then this makes an omniscient creature that can 'know' the future far more problematic as our choices have a direct causal impact on the universe, meaning that from any decision we make the future of the universe is less and less certain as we predict further out.
To Address Additional Question in OP
Certainly in a non-deterministic universe, being able to make any statement about the future with certainty could only occur if one knew the relevant information about every possible state at every point in time of the universe, and this would appear to be a paradox because of free will but for the sake of the argument, let's say the paradox does not exist, then this kind of omniscience wouldn't involve knowing how the universe works, just all information about its state at any given point in time.
On the other hand, in a deterministic environment, making a true inductive statement about the future does not require that kind of omniscience, but it would involve the omniscience of knowing;
1) All information about the state of the universe at a given point in time
2) All information about the deterministic rules employed by the universe
One could argue that is in itself potential omniscience; having the information to deduce the state of the universe at any given point in time without actually having done so yet. The situation is analogous to us sitting down with pen and paper to work out the product of 11,218 and 30,669,287. We know the starting figures, we know how to do the arithmetic to derive their product; all that remains is actually doing the math. In that instance, we hold the potential to know the answer, without actually knowing it yet.
So, the determining constraints on an omniscient creature are as follows;
1) How simple can we make the universal model without losing integrity
2) How far in the future do you want to peer
3) Whether or not the universe is subject to true determinism
4) Whether you want your omniscient being to be able to communicate with others
Like everything, the limits (or lack thereof) determine how close you can get to the ideal in this instance.