Let's say I have a function simulate() that returns True with some probability $p$ and False otherwise.
After calling simulate() $N$ times, I get True $x$ times and False $N - x$ times. I then compute $p' = \frac{x}{N}$. How do I measure my error on $p'$? My ultimate goal is to figure out whether $p > 0.5$ for my simulate() function, and I want to know how many trials I have to conduct to be confident in my result.
Your data are independent binary variables with a fixed probability, so the count value you are seeking is a binomial random variable. You already have a point estimate, so the next step is to use an appropriate interval estimator, such as a confidence interval. This is a very well-known problem, so I recommend you start by reading some textbook presentations of binomial confidence intervals. You can also read Brown et al (2001) for an overview of available methods, and comparison between methods.
By virtue of the fact that $X$ has a binomial distribution, we know that the standard error for $p'$ is $p(1-p)/N$. Now $p$ is the unknown variable we wish to estimate so we get an estimate by replacing $p$ with $p'$. If $N$ is large enough we can use a normal approximation for $p'$ and take $\pm 2$ estimated standard deviations around $p'$ as an approximate 95% confidence interval for $p'$. This would be a two-sided interval. Since you only want to know if $p>0.5$, you might prefer using a one-sided interval.
You are working with a binomial distribution. Its variance for a sample of n observations with a "p" chance of getting a "true result" is np(1-p)
Therefore its standard deviation will be the square root of np(1-p) (use the results you got before to estimate p, ie: use the sample p as "kind-of-the-true-p") You can now calculate confidence intervals and all those cool things you can do with normal distributions (for a large enough sample, it will behaive similarly)
