OK, i'm adding to the original question; Shouldn't all drawing be done in the OnPaint() event?
If so, how would you implement this program properly?
If not, is the code below legal/proper in every way?
Also, the code below does not handle rezising/minimizing of the window, what is the best way to fix that?
Here's How I got it to work, just paste it onto a form with the appropriate eventhandlers declared (Based on mule's code):

bool _drawing = false;
Point _lastPoint;
Point _newPoint;
private void Form1_MouseUp(object sender, MouseEventArgs e)
{
    if (e.Button == MouseButtons.Left)
    {
        //Are these really necessary?
        //this.MouseUp -= new //System.Windows.Forms.MouseEventHandler(this.Picture_MouseUp);
        //this.MouseMove -= new //System.Windows.Forms.MouseEventHandler(this.Picture_MouseMove);

        if (_drawing)
        {
            _newPoint = new Point(e.X, e.Y);
            DrawLine(_lastPoint, _newPoint, this.CreateGraphics());
        }
        _drawing = false;
    }
}

private void Form1_MouseMove(object sender, MouseEventArgs e)
{
    if (_drawing)
    {
        _lastPoint = _newPoint;
        _newPoint = new Point(e.X, e.Y);
        DrawLine(_lastPoint, _newPoint, this.CreateGraphics());
    }
}

private void Form1_MouseDown(object sender, MouseEventArgs e)
{
    if (e.Button == MouseButtons.Left)
    {
        _drawing = true;
        _lastPoint = new Point(e.X, e.Y);
        _newPoint = new Point(e.X, e.Y);

        //Again, are these really neccesary?
        //this.MouseMove += new  //System.Windows.Forms.MouseEventHandler(this.Picture_MouseMove);
        //this.MouseUp += new //System.Windows.Forms.MouseEventHandler(this.Picture_MouseUp);

    }
}

private void DrawLine(Point from, Point to)
{
    Graphics g = this.CreateGraphics();
    g.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.HighQuality;
    Pen p = new Pen(Color.Red, 5);//Just to make it look nice
    p.StartCap = System.Drawing.Drawing2D.LineCap.Round;//Just to make it look nice
    p.EndCap = System.Drawing.Drawing2D.LineCap.Round;//Just to make it look nice
    g.DrawLine(p, from, to);
    g.Dispose();
    p.Dispose();
}